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 <ipse...@gmail.com> 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. >
