import random
def gcd(a: int, b: int):
"""Euclidean algorithm finds the greatest common divisor""""
while a != 0:
a, b = b % a, a
return b
def euler(n):
"""Euler function"""
# If n is a prime number, return directly to n-1
if (n, 1) == 1:
return n - 1
m = 0
for i in range(n):
if gcd(i, n) == 1:
m += 1
return m
def getFirstPrimitiveRoot(p):
""" Calculate the first original root"""
# Get the Euler function value m
euler_n = euler(p)
#Double loop
for a in range(2, p):
for m in range(2, p):
# The first m satisfies a^m = 1 mod p At the same time m = euler_n, then a is the first original root
if pow(a, m, p) == 1:
# If the smallest positive power a is not an Euler function, the next cycle will be performed
if m == euler_n:
return a
else:
break
return False
def getAllPrimitiveRoot(p, first):
primitiveRoot = []
for i in range(p):
# If i and p are mutually exclusive, i is a simplified remaining member of p-1
if gcd(i, p - 1) == 1:
# Add original root to the list
primitiveRoot.append(pow(first, i, p))
return primitiveRoot
if __name__ == '__main__':
p = 41
firstp = getFirstPrimitiveRoot(p)
pR = getAllPrimitiveRoot(p, firstp)
print(pR)
# Randomly select a native root g
g = pR[random.randint(0, len(pR) - 1)]
# Generate a random x
x = random.randint(1, p - 2)
# Calculate y = g^x mod p
y = pow(g, x, p)
print(f"Expose (p,g,y):{(p, g, y)}")
print(f"Secretly save x:{x}")
