Integer factorization

We will see three algorithms for integer factorization: the Pollard $p-1$ algorithm, the Pollard $\rho$ algorithm, and Dixon's random squares algorithm.

In [1]:
from algorithms.factorization import pollardP1, pollardRho, totalFactorization, factorizeByBase

Pollard $p-1$ algorithm

Let us try to determine the bound $B$ needed to factor $262063$ and $9420457$.

In [10]:
pollardP1(262063, 13)
Out[10]:
521
In [11]:
521.is_prime()
Out[11]:
True
In [13]:
520.factor()
Out[13]:
2^3 * 5 * 13
In [14]:
262063 / 521
Out[14]:
503
In [15]:
503.is_prime()
Out[15]:
True
In [16]:
502.factor()
Out[16]:
2 * 251
In [19]:
pollardP1(9420457, 47)
Out[19]:
2351
In [20]:
2351.is_prime()
Out[20]:
True
In [21]:
2350.factor()
Out[21]:
2 * 5^2 * 47

Pollard $\rho$ algorithm

Let us try to factor $221$ using the function $f(x) = (x^2 + 1) \bmod{221}$.

In [29]:
n = 221
f = lambda x: (x^2 + 1) % n
pollardRho(n, f, trace=True)
x = 194
f(x) = 67
gcd(x-f(x), n) = 1
f^1(x) = 67
f^3(x) = 39
gcd(f^1(x)-f^3(x), n) = 1
f^2(x) = 70
f^5(x) = 184
gcd(f^2(x)-f^5(x), n) = 1
f^3(x) = 39
f^7(x) = 169
gcd(f^3(x)-f^7(x), n) = 13
Out[29]:
13
In [23]:
221 / 13
Out[23]:
17

Dixon's random squares algorithm

We will factorize $n = 15770708441$ using the random integers $14056852462$, $9004436975$, $5286195500$, $11335959904$ and $7052612564$. Let us factorize the squares of the random integers modulo $n$. We notice that they can be expressed as products of powers of the smallest seven primes.

In [30]:
n = 15770708441
r = [14056852462, 9004436975, 5286195500, 11335959904, 7052612564]
b = [2, 3, 5, 7, 11, 13, 17]
fac = [factorizeByBase(x^2 % n, b, n) for x in r]
fac
Out[30]:
[[1, 3, 0, 0, 0, 3, 2],
 [0, 2, 3, 8, 0, 0, 0],
 [2, 3, 0, 3, 0, 2, 0],
 [4, 0, 4, 0, 1, 0, 4],
 [0, 8, 1, 0, 1, 2, 0]]

Let us gather the exponents into a matrix.

In [31]:
M = Matrix(fac)
M
Out[31]:
[1 3 0 0 0 3 2]
[0 2 3 8 0 0 0]
[2 3 0 3 0 2 0]
[4 0 4 0 1 0 4]
[0 8 1 0 1 2 0]
In [32]:
sum(M[[1, 3, 4], :])
Out[32]:
(4, 10, 8, 8, 2, 2, 4)

We notice that summing the second and the last two rows gives a vector consisting entirely of even numbers.

In [33]:
rows = (1, 3, 4)
[sum(M[rows, i]) % 2 for i in range(len(b))]
Out[33]:
[(0), (0), (0), (0), (0), (0), (0)]

We can use this to find a factor of $n$.

In [34]:
pr = prod(r[i] for i in rows) % n
pb = prod(p^e for p, (e, ) in zip(b, (sum(M[rows, i])/2 for i in range(len(b))))) % n
g = gcd(abs(pr - pb), n)
(g, n/g)
Out[34]:
(135979, 115979)