Pollard rho has too many loops?

[mhostetter]

It looks like 2**256-1 factorization as implemented currently gets to the point where it needs to factorize 340282366920938463463374607431768211457==2**128+1 which is 59649589127497217 * 5704689200685129054721. Unfortunately, it looks like Pollard's rho algorithm is getting much more than usual time for this number for offset c=1 (not sure why - square root of the smallest factor is ~24M but it seems that it takes around 455M steps for Pollard's rho to find the factor). That said running pollard_rho with c=3 finds the factor after 19M iterations which is close to regular working times of Pollard's rho.

Copied from #187 (comment).

[mhostetter]

In [1]: import galois

In [2]: %time galois.pollard_rho(59649589127497217 * 5704689200685129054721)
Pollard Rho found a factor 59649589127497217 of 340282366920938463463374607431768211457 in 455,756,940 loops.
Wall time: 16min 46s
Out[2]: 59649589127497217

In [3]: %time galois.pollard_rho(59649589127497217 * 5704689200685129054721, c=3)
Pollard Rho found a factor 59649589127497217 of 340282366920938463463374607431768211457 in 19,246,066 loops.
Wall time: 43.3 s
Out[3]: 59649589127497217