rho, rho, rho your boat

The Pollard's rho algorithm is one way of factoring such a number which has an expected running time proportional to the square root of the smallest prime factor of the composite number.

The proof of the algorithm is as follows:

Consider $N = pq$ , the Euler-Fermat theorem states that, $a^{p-1} \equiv 1 \pmod p$ for all $a$ relativelly prime to $p$ . Suppose $p-1$ is a factor of $L$ . Then $L = (p-1)k$ , so:

$a^L \equiv (a^{p-1})^k \pmod p \equiv 1 \pmod p$

So $p$ divides $a^L - 1$ , since $p$ is a factor os $N$ , the $GCD$ of $a^L - 1$ and $N$ must include N.

If $L = k!$ then it must include $p-1$ as one of its factors for a large enough $k$ .

The algorithm consists as follow:

• Choose a prime a, so that $a^{p-1} \equiv 1 \pmod p$ and a number k
• Compute $a^{k!} \pmod N$
• Check $GCD(a^{k!}, N) = 1$
• If it isn't, then it's a factor of $N$
• If it is, increase $k$ and try again until reach an answer.

Since $N = p*q$ we can simply get the other factor by computing $\frac{N}{p}$ , doing so, we get:

$p$ = 48112959837082048697

$q$ = 54673257461630679457

$p+q$ = 102786217298712728154

Here is my Python implementation of the algorithm:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

N = 2630492240413883318777134293253671517529

def gcd(x, y):
    return y if not (x%y) else gcd(y, x%y)

def pollard_rho(N):
    a = 2
    k = 1
    gcd_N = gcd(a - 1, N)
    while gcd_N == 1:
        a = pow(a, k, N)
        gcd_N = gcd(a - 1, N)
        k += 1
    return gcd_N

p = pollard_rho(N)
q = N // p
print(p+q)