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
|
"""
This module holds a fast Factorization class.
"""
from random import randint
class Factorization:
"""
Simple module to factorize large numbers really quickly.
"""
@classmethod
def factorize(cls, pq):
"""
Factorizes the given large integer.
Implementation from https://comeoncodeon.wordpress.com/2010/09/18/pollard-rho-brent-integer-factorization/.
:param pq: the prime pair pq.
:return: a tuple containing the two factors p and q.
"""
if pq % 2 == 0:
return 2, pq // 2
y, c, m = randint(1, pq - 1), randint(1, pq - 1), randint(1, pq - 1)
g = r = q = 1
x = ys = 0
while g == 1:
x = y
for i in range(r):
y = (pow(y, 2, pq) + c) % pq
k = 0
while k < r and g == 1:
ys = y
for i in range(min(m, r - k)):
y = (pow(y, 2, pq) + c) % pq
q = q * (abs(x - y)) % pq
g = cls.gcd(q, pq)
k += m
r *= 2
if g == pq:
while True:
ys = (pow(ys, 2, pq) + c) % pq
g = cls.gcd(abs(x - ys), pq)
if g > 1:
break
p, q = g, pq // g
return (p, q) if p < q else (q, p)
@staticmethod
def gcd(a, b):
"""
Calculates the Greatest Common Divisor.
:param a: the first number.
:param b: the second number.
:return: GCD(a, b)
"""
while b:
a, b = b, a % b
return a
|
