Timeline for Fastest way to factor integers < 2^60
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 23, 2012 at 7:19 | comment | added | Ng Yong Hao | @quid Oh I did not know that! That explains why I see so many papers there. Thanks for the clarification. =D | |
| Nov 22, 2012 at 19:10 | comment | added | user9072 | Thank you for the reply and the information! (Just a tangential note in case it interests you: HAL, where the paper is hosted is sort-of a French arXiv; just that a paper is there does not imply any relation to INRIA. It seems however true that all the ones you mentioned are from people more directly affiliated with INRIA, in the sense of employed by this (academic) institution, which I think means roughly the same as it would mean if they were employed by some given university). | |
| Nov 22, 2012 at 16:52 | history | edited | Ng Yong Hao | CC BY-SA 3.0 |
added 28 characters in body
|
| Nov 22, 2012 at 16:07 | history | edited | Ng Yong Hao | CC BY-SA 3.0 |
Added another solution involving lookup table
|
| Nov 22, 2012 at 15:18 | comment | added | Ng Yong Hao | @quid I have some figures: it takes 0.025 sec on my x64 2.00 GHz laptop to run 20 curves to factor primes $<2^{32}$, but it takes negligible time to trial divide up to 500000. I can probably increase the limit a little more, up to a point where the run time is significant. But the expected efficiency is small, so I think there is probably not much difference anyway. So upon reflection: 500000 as a limit seems like a decent idea. I think the ideal number also depends on the range ECM handles. In this case the small primes will be found by the curves, so the limit does not need to be that high. | |
| Nov 22, 2012 at 12:57 | comment | added | Ng Yong Hao | @quid Roughly speaking, suppose I aim to trial divide a range of primes. Then equivalently, I can set a set of 20 curves to find that same range (20 curves to get a high prob. of >0.95). So any time the 20 curves takes less time than the trial division, switching to ECM is faster. Unfortunately I did not find that leveling point. Also, I agree that given OP's range, after trial testing the small ones the case is usually the same as the paper (2-4 factors) so SQUFOF seems like the better choice. My suggestions/comments are for the case when he wants to do it via ECM. | |
| Nov 22, 2012 at 12:37 | comment | added | Ng Yong Hao | @quid I am not too sure how the association works. I mentioned INRIA since the papers are usually hosted by its webpages and it appears that the authors are linked to the organization. But I guess you are right, probably more correct to quote Jérôme Milan instead. As for trial division testing beyond $2^{10}$ (not sure what actual values are) does not seem very effective. It is still good to trial test the very small ones though, since the time taken is negligible; It should be the medium ones that should not be tested by trial division. | |
| Nov 22, 2012 at 7:20 | comment | added | user9072 | the advantage if SQUFOF up to 50 bit seems quite drastic (in the graphic this looks like an order of magnitude) and stays very large for up to 55 bits; and in reality OP is doing it seems not 60 bit but 57 max, and possibly often even less due to the algebraic factorization being present. | |
| Nov 22, 2012 at 7:15 | comment | added | user9072 | Thanks for the interesting paper. I just find it puzzling you say INRIA has published a paper; this seems like a normal preprint by Jérôme Milan (who happens to be affiliated with INRIA). A quick question: do you suggest to run GMP-ECM without any prior trial divison for very small factors? This seems surpring to me, but I could well be wrong. If not, what would you suggest as very small? (My point is I took the 500000 from Cohen, but if one would even only go to 10000, one would be essential in a four-factor situation already, then). Also, ... | |
| Nov 22, 2012 at 4:34 | history | answered | Ng Yong Hao | CC BY-SA 3.0 |