HP 41C Pollard Brent Integer Factorization

07062014, 05:41 AM
Post: #3




RE: HP 41C Pollard Brent Integer Factorization
(07052014 09:11 PM)Joe Horn Wrote: POBR takes 1.5 minutes to factor 503*509, whereas the bruteforce NP program in the PPC ROM takes only 1 minute. This is very strange, since it seems to me that no method should take longer than bruteforce trial and error. For some numbers the Rho method will take longer than other numbers of a similar magnitude. The programme takes a pseudorandom path governed by a polynomial, in our case initially x^2+1 (if this fails to find a proper factor, then x^2+2, then x^2+3,...), modulo the number to be factored. The starting point is 2, line eleven of the programme. A different starting point will produce correspondingly different timings for factorization. For example, the number K=9,999,399,973 is factored by the prog as here published after 439 squarings, or about 37 minutes on a real 41C. Using other values in line eleven of the prog produces other times, mostly shorter. Irritatingly it's hard to tell which seed value will prove best before trying it for a particular factoree. I use a variant of the published prog, replacing line eleven with a random numer generator  this produces erratic timings, but makes the procedure more interesting. How long do you think K would require for factorization by brute force? 

« Next Oldest  Next Newest »

Messages In This Thread 
HP 41C Pollard Brent Integer Factorization  Gerald H  07042014, 07:07 PM
RE: HP 41C Pollard Brent Integer Factorization  Joe Horn  07052014, 09:11 PM
RE: HP 41C Pollard Brent Integer Factorization  Gerald H  07062014 05:41 AM
RE: HP 41C Pollard Brent Integer Factorization  Gerald H  07062014, 06:55 AM
RE: HP 41C Pollard Brent Integer Factorization  Joe Horn  07072014, 05:55 AM
RE: HP 41C Pollard Brent Integer Factorization  Jim Horn  07072014, 06:04 AM
RE: HP 41C Pollard Brent Integer Factorization  Joe Horn  07072014, 12:02 PM
RE: HP 41C Pollard Brent Integer Factorization  Gerald H  07072014, 12:27 PM
RE: HP 41C Pollard Brent Integer Factorization  Joe Horn  07082014, 06:20 AM

User(s) browsing this thread: 1 Guest(s)