search

mhostetter / galois

A performant NumPy extension for Galois fields and their applications
https://mhostetter.github.io/galois/
MIT License
325 stars 29 forks source link

Pollard rho has too many loops? #453

Open mhostetter opened 1 year ago

mhostetter commented 1 year ago

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 https://github.com/mhostetter/galois/issues/187#issuecomment-1346103086.

mhostetter commented 1 year ago 
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