Thanks for the input. My deterministic Pollard Rho does: F6: 2.0 milliseconds
F7: failure F8: 6.98 seconds 2015-11-04 21:34 GMT+01:00 Julia Users mailing list [via Julia Programming Language] <[email protected]>: > It would be better with Pollard Rho to list the times depending on the > smallest factor. > > It would be interesting to compare timings for some known numbers such as > Fermat numbers (F_n = 2^(2^n) + 1). > > Here are some timings from a Google summer of code project we had this > year: > > F_6 (18446744073709551617) > pollard rho : 0.001583 seconds > ECM : 0.012700 seconds > > F_7 (340282366920938463463374607431768211457) > pollard rho : 113.476116 seconds > ECM : 0.613939 seconds > > F_8 > (115792089237316195423570985008687907853269984665640564039457584007913129639937) > pollard rho : 47.584017 seconds > ECM : 0.292101 seconds > > It's possible he improved the timings a little later, but these should > serve as a guide anyway. > > Bill. > > On 4 November 2015 at 21:16, janvanoort <[hidden email] > <http:///user/SendEmail.jtp?type=node&node=30871&i=0>> wrote: > >> You are right. What I mean, is that my Pollard Rho is completely >> deterministic. >> >> Times for ranges of numbers: >> >> bitlength < 20 >> 100 µs - 300 µs >> 20 < bit length < 40 >> around 3 ms >> random numbers with bitlength ~1024 >> 3 ms - 800 ms, depending on size of smallest prime factor >> ( for this post, in order to check, I just made it factor the Mersenne >> number 2^1117-1; it came up with the factor 53617 in 860 ms ) >> >> >> >> >> >> 2015-11-04 20:57 GMT+01:00 Julia Users mailing list [via Julia >> Programming Language] <[hidden email] >> <http:///user/SendEmail.jtp?type=node&node=30868&i=0>>: >> >>> Do you mean you are factoring something other than random numbers, or do >>> you mean your Pollard Rho is completely deterministic? >>> >>> It's not a good measure of performance to time just one factorisation >>> with Pollard Rho, since you could just pick the parameters such that it >>> essentially succeeds immediately. You should give times for a range of >>> numbers. >>> >>> Bill. >>> >>> On 4 November 2015 at 18:55, janvanoort <[hidden email] >>> <http:///user/SendEmail.jtp?type=node&node=30867&i=0>> wrote: >>> >>>> That's interesting. I have been working for a week now on a somewhat >>>> improved >>>> version of Pollard's Rho, by "feeding" it with something else than a >>>> random >>>> number, in order to take away the non-deterministic behaviour. My >>>> implementation is written in Java 8 ( have had no time to port it to >>>> Julia, >>>> yet ), and factors 3^100+2 in about 800 milliseconds an a Xeon E3-1265L >>>> with >>>> 8 MB cache, on Linux ( Ubuntu Server ). If anyone's interested, feel >>>> free to >>>> ping me. >>>> >>>> >>>> >>>> -- >>>> View this message in context: >>>> http://julia-programming-language.2336112.n4.nabble.com/Factorization-of-big-integers-is-taking-too-long-tp15925p30844.html >>>> Sent from the Julia Users mailing list archive at Nabble.com. >>>> >>> >>> >>> >>> ------------------------------ >>> If you reply to this email, your message will be added to the discussion >>> below: >>> >>> http://julia-programming-language.2336112.n4.nabble.com/Factorization-of-big-integers-is-taking-too-long-tp15925p30867.html >>> To unsubscribe from Factorization of big integers is taking too long, click >>> here. >>> NAML >>> <http://julia-programming-language.2336112.n4.nabble.com/template/NamlServlet.jtp?macro=macro_viewer&id=instant_html%21nabble%3Aemail.naml&base=nabble.naml.namespaces.BasicNamespace-nabble.view.web.template.NabbleNamespace-nabble.view.web.template.NodeNamespace&breadcrumbs=notify_subscribers%21nabble%3Aemail.naml-instant_emails%21nabble%3Aemail.naml-send_instant_email%21nabble%3Aemail.naml> >>> >> >> >> ------------------------------ >> View this message in context: Re: Factorization of big integers is >> taking too long >> <http://julia-programming-language.2336112.n4.nabble.com/Factorization-of-big-integers-is-taking-too-long-tp15925p30868.html> >> >> Sent from the Julia Users mailing list archive >> <http://julia-programming-language.2336112.n4.nabble.com/Julia-Users-f2.html> >> at Nabble.com. >> > > > > ------------------------------ > If you reply to this email, your message will be added to the discussion > below: > > http://julia-programming-language.2336112.n4.nabble.com/Factorization-of-big-integers-is-taking-too-long-tp15925p30871.html > To unsubscribe from Factorization of big integers is taking too long, click > here > <http://julia-programming-language.2336112.n4.nabble.com/template/NamlServlet.jtp?macro=unsubscribe_by_code&node=15925&code=aXBzZWphbkBnbWFpbC5jb218MTU5MjV8ODc1MDMwODkz> > . > NAML > <http://julia-programming-language.2336112.n4.nabble.com/template/NamlServlet.jtp?macro=macro_viewer&id=instant_html%21nabble%3Aemail.naml&base=nabble.naml.namespaces.BasicNamespace-nabble.view.web.template.NabbleNamespace-nabble.view.web.template.NodeNamespace&breadcrumbs=notify_subscribers%21nabble%3Aemail.naml-instant_emails%21nabble%3Aemail.naml-send_instant_email%21nabble%3Aemail.naml> > -- View this message in context: http://julia-programming-language.2336112.n4.nabble.com/Factorization-of-big-integers-is-taking-too-long-tp15925p30873.html Sent from the Julia Users mailing list archive at Nabble.com.
