# 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 :
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 :
pollardP1(262063, 13)

Out:
521
In :
521.is_prime()

Out:
True
In :
520.factor()

Out:
2^3 * 5 * 13
In :
262063 / 521

Out:
503
In :
503.is_prime()

Out:
True
In :
502.factor()

Out:
2 * 251
In :
pollardP1(9420457, 47)

Out:
2351
In :
2351.is_prime()

Out:
True
In :
2350.factor()

Out:
2 * 5^2 * 47

## Pollard $\rho$ algorithm¶

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

In :
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:
13
In :
221 / 13

Out:
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 :
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:
[[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 :
M = Matrix(fac)
M

Out:
[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 :
sum(M[[1, 3, 4], :])

Out:
(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 :
rows = (1, 3, 4)
[sum(M[rows, i]) % 2 for i in range(len(b))]

Out:
[(0), (0), (0), (0), (0), (0), (0)]

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

In :
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:
(135979, 115979)