#!/usr/bin/env python
# coding: utf-8

# # 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)


# In[11]:


521.is_prime()


# In[13]:


520.factor()


# In[14]:


262063 / 521


# In[15]:


503.is_prime()


# In[16]:


502.factor()


# In[19]:


pollardP1(9420457, 47)


# In[20]:


2351.is_prime()


# In[21]:


2350.factor()


# ## 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)


# In[23]:


221 / 13


# ## 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


# Let us gather the exponents into a matrix.

# In[31]:


M = Matrix(fac)
M


# In[32]:


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


# 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)