"Pollard's rho algorithm" someone sent me this as a way to go at 66 is a way.

this is what ive kinda read up on so far about it. for anyone wondering if they don't know read below.


In the paper "A monte carlo method for factorization", Pollard introduces a method for factoring composite numbers that is better than trial division. The main idea is to generate random numbers and test if the difference between any pair has a non-1
 divisor in common with the number to be factored, which exploits the birthday paradox to find factors faster than trial division.

In his paper, Pollard uses the formula: xi+1≡x2i−1modn
, to generate random numbers, where n
 is the number that we want to factor and x0=2
. He notes that any polynomial of degree ≥2
 can be used.

It intuitively makes sense to me that linear functions can have additional properties that cause the generated sequence to not be random enough. However, I see no clear reason why the algorithm would only work for polynomials. Using different functions, for example with bit manipulations and storing intermediate results modulo 264
 could potentially make the algorithm faster on real computers.