1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
|
def gcd(a, b):
while b != 0:
(a,b) = (b, a%b)
return a
def factorize(n, wheel=3):
if n < 2:
return []
primes = (2, 3, 5, 7, 11)
if wheel < 2 or wheel > len(primes):
wheel = 3
primes = primes[:wheel]
q = []
for p in primes:
if n % p != 0:
continue
e = 1
n //= p
while n % p == 0:
n //= p
e += 1
q.append((p, e))
if n > 1:
m = reduce(lambda x, y:x*y, primes, 1)
offs = [x for x in xrange(2, m + 1) if gcd(m, x) == 1] + [m + 1]
k, done = 0, False
while n > 1:
for offset in offs:
p = k + offset
if p ** 2 > n:
done = True
break
if n % p != 0:
continue
e = 1
n //= p
while n % p == 0:
n //= p
e += 1
q.append((p, e))
if done:
break
k += m
if n > 1:
q.append((n, 1))
return q
def Euler(n, wheel=3):
''' Euler Totient Function of n using a prime wheel criterion.
It's almost as fast as the phi(n, p) function '''
if n < 2:
return n
q = factorize(n, wheel)
r = 1
for (p, e) in q:
r *= (p - 1) * (p ** (e - 1))
return r
def primitive_root(mod):
simple = []
root = []
phi_m = Euler(mod)
for i in range(1,mod):
if gcd(i, mod) == 1:
simple.append(i)
for a in simple:
for j in range(1,phi_m+1):
if a ** j % mod == 1:
if j == phi_m:
root.append(a)
else:
break
return root
if __name__ == '__main__':
mod = raw_input('Please input mod:')
print primitive_root(int(mod))
|
