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]:

In [11]:

521.is_prime()

Out[11]:

True

In [13]:

520.factor()

Out[13]:

2^3 * 5 * 13

In [14]:

262063 / 521

Out[14]:

In [15]:

503.is_prime()

Out[15]:

True

In [16]:

502.factor()

Out[16]:

2 * 251

In [19]:

pollardP1(9420457, 47)

Out[19]:

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]:

In [23]:

221 / 13

Out[23]:

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)