HP 41C Pollard Brent Integer Factorization

[Gerald H]

(07-06-2014 05:41 AM)Gerald H Wrote:  

(07-05-2014 09:11 PM)Joe Horn Wrote:  POBR takes 1.5 minutes to factor 503*509, whereas the brute-force 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 brute-force trial and error.

Also, POBR never seems to finish with even moderate-sized inputs, such as 991*997.

Is this expected, or evidence of a bug? (I double-checked to be sure that I keyed your programs in correctly.)

For some numbers the Rho method will take longer than other numbers of a similar magnitude.

The programme takes a pseudo-random 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?

I have now run the factorization of K 204 times using a succession of random numbers for line 11 of the programme, resulting in an average number of squarings of 251 with a standard deviation of 153, implying a 99% confidence range of 223 to 279 squarings, should the time for factorization be normally distributed.

So it looks like 2 is a particularly bad seed for the number K.