Timeline for Fastest way to factor integers < 2^60
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 22, 2012 at 13:02 | comment | added | Roland Bacher | One could perhaps combine trial division with a few iterations of Pollard's $\rho-$method: $N=1000$ iterations (or perhaps $2000$ or $3000$) of $\rho$ should catch most prime-factors smaller than $500000$. Fixing a $\rho-$method, one can precompute a (presumably) small list of primes smaller than $500000$ not catched by $N$ iterations of $\rho$. I have however not checked whether this is faster for random elements of size $\sim 2^{60}$ for suitable choices of $N$ and of a $\rho-$method. (A fixed $\rho-$method will of course not always give a complete factorization.) | |
| Nov 21, 2012 at 23:03 | history | edited | user9072 | CC BY-SA 3.0 |
significantly expanded
|
| Nov 21, 2012 at 20:16 | comment | added | Kevin Acres | @Quid: I've got the book and I'll have a look later. Many thanks. | |
| Nov 21, 2012 at 20:04 | comment | added | user9072 | @Hurkly: I will come back to this in more detail in two hours or so but I have a 2008 quote handy that says on 32bit SQUOFOF is 'clear champion' in 10^10 to 10^18 range. | |
| Nov 21, 2012 at 19:19 | comment | added | user13113 | While SQUFOF is good, I confess that I would have expect a good ECM implementation to become better before the $2^{60}$ cutoff. | |
| Nov 21, 2012 at 14:15 | comment | added | user9072 | A rough inspection of flint mentioned by William Hart in a comment suggests that indeed it uses SQUFOF above 2^40 , below it uses a Fermat variant due to him; combined with trial divisions and perfact power checks. (I hope I got this right; the main purpose of this is to reassure myself my answer is not off.) | |
| Nov 21, 2012 at 11:58 | history | answered | user9072 | CC BY-SA 3.0 |