-
Notifications
You must be signed in to change notification settings - Fork 0
/
task10.py
48 lines (37 loc) · 1017 Bytes
/
task10.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
from math import gcd
from sys import argv
from prime import factorize
def f(x, n):
return (pow(x, 2, n) + 1) % n
def p_pollard(n, c):
c = c % n
a = b = c
values = {c}
a = f(a, n)
b = f(f(b, n), n)
while True:
d = gcd((a - b) % n, n)
if 1 < d < n:
return d
elif d == n:
return -1
a = f(a, n)
b = f(f(b, n), n)
if a in values or b in values:
return -1
def main():
if len(argv) == 1:
n = int(input('Введите n = '))
c = int(input('Введите с = ')) % n
assert 1 < c < n, 'c должно быть 1 < c < n'
elif len(argv) == 2:
n = int(argv[1])
c = int(input('Введите с = ')) % n
else:
n = int(argv[1])
c = int(argv[2]) % n
assert 1 < c < n, 'c должно быть 1 < c < n'
factors = factorize(n, p_pollard, c)
print('\n'.join(map(str, factors.items())))
if __name__ == '__main__':
main()