-
Notifications
You must be signed in to change notification settings - Fork 0
/
ent_class.py
56 lines (46 loc) · 1.27 KB
/
ent_class.py
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
import ent
class Ent:
classvar = "classvarvalue"
def __init__(self):
self.enabled = False
def enable(self, x, y=None):
self.enabled = x and x.value and y and y.value
def x(self, X):
self.X = X
def trial_division(self, n, bound=None):
assert self.enabled
return ent.trial_division(n, bound=bound)
def powermod(self, a, m, n):
assert self.enabled
return ent.powermod(a, m, n)
def factor(self, n):
assert self.enabled
if n in [-1, 0, 1]: return []
if n < 0: n = -n
F = []
while n != 1:
p = self.trial_division(n)
e = 1
n /= p
while n%p == 0:
e += 1; n /= p
F.append((p,e))
F.sort()
return F
def primitive_root(self, p):
assert self.enabled
if p == 2: return 1
F = self.factor(p-1)
a = 2
while a < p:
generates = True
for q, _ in F:
if self.powermod(a, (p-1)/q, p) == 1:
generates = False
break
if generates: return a
a += 1
assert False, "p must be prime."
class InsideEnt:
def x(self, x):
self.value = x