HP 41C Pollard Brent Integer Factorization

[Gerald H]

I don't know if anyone did this in the dark ages, but here's my try at this factorizing method.

POBR has 2 sub-programmes, see below.

POBR takes a composite integer from the stack & returns one integer factor.

0. LBL POBR
1. STO 01
2. CHS
3. STO 00
4. CLX
5. STO 02
6. LBL 02
7. SIGN
8. ST+ 02
9. STO 04
10. STO 05
11. 2
12. LBL 00
13. RCL 04
14. STO 05
15. RDN
16. STO 03
17. LBL 03
18. XEQ SQM
19. RCL 02
20. +
21. STO Y
22. RCL 03
23. –
24. RCL 01
25. XEQ GCF
26. 1
27. X≠Y?
28. GTO 01
29. RCL Z
30. DSE 05
31. GTO 03
32. RCL 04
33. RCL X
34. +
35. STO 04
36. STO 05
37. RDN
38. LBL 04
39. XEQ SQM
40. RCL 02
41. +
42. DSE 05
43. GTO 04
44. GTO 00
45. LBL 01
46. R↓
47. RCL 01
48. X<>Y
49. X=Y?
50. GTO 02
51. BEEP
52. END

SQM returns the square of the X register modulo register 01.

0. LBL SQM
1. STO Y
2. 1E5
3. MOD
4. STO Z
5. –
6. ENTER
7. X^2
8. RCL 00
9. MOD
10. X<>Y
11. R↑
12. ST* T
13. *
14. RCL 01
15. MOD
16. STO 06
17. RCL L
18. -
19. RCL 06
20. +
21. RCL 01
22. MOD
23. +
24. RCL 00
25. MOD
26. +
27. RCL 01
28. MOD
29. END

GCF returns the greatest common divisor of registers X & Y.

0. LBL GCF
1. LBL 00
2. MOD
3. LASTX
4. X<>Y
5. X≠0?
6. GTO 00
7. RDN
8. ABS
9. END

[Joe Horn]

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.)

[Gerald H]

(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?

[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.

[Joe Horn]

(07-06-2014 05:41 AM)Gerald H Wrote:  How long do you think K would require for factorization by brute force?

Based on the speed of NP in the PPC ROM, roughly 38 years, which would mean that I would probably terminate before NP did.

[Jim Horn]

A modulo 210 brute force factoring on the HP-67 took 0.1042*sqrt(x) seconds in 1979. The HP-41 averaged 3 times that speed. So your example would take around 58 minutes. (CF "Finding Factors Faster", PPC Journal, mid-Cretaceous epoch, by some old phart)

[Joe Horn]

(07-07-2014 06:04 AM)Jim Horn Wrote:  A modulo 210 brute force factoring on the HP-67 took 0.1042*sqrt(x) seconds in 1979. The HP-41 averaged 3 times that speed. So your example would take around 58 minutes. (CF "Finding Factors Faster", PPC Journal, mid-Cretaceous epoch, by some old phart)

Cool. Oh yeah, I forgot that it only needs to go up to the square root of the input, not the whole way. So instead of NP taking 38 years, it should take about 3 hours 20 minutes. Quite a difference!

[Gerald H]

(07-07-2014 12:02 PM)Joe Horn Wrote:  

(07-07-2014 06:04 AM)Jim Horn Wrote:  A modulo 210 brute force factoring on the HP-67 took 0.1042*sqrt(x) seconds in 1979. The HP-41 averaged 3 times that speed. So your example would take around 58 minutes. (CF "Finding Factors Faster", PPC Journal, mid-Cretaceous epoch, by some old phart)

Cool. Oh yeah, I forgot that it only needs to go up to the square root of the input, not the whole way. So instead of NP taking 38 years, it should take about 3 hours 20 minutes. Quite a difference!

So 3 hrs 20 mins versus 37 mins with a bad seed choice.

Is the NP programme written in a lower level language?

Where can I find documentation on "Finding Factors Faster"?

If you're interested, have a look at the performance of POBR on the WP 34S.

[Joe Horn]

(07-07-2014 12:27 PM)Gerald H Wrote:  Is the NP programme written in a lower level language?

No. 100% standard HP-41 user language, not even any synthetics. Listing can be found on page 347 of the PPC ROM User's Manual.

(07-07-2014 12:27 PM)Gerald H Wrote:  Where can I find documentation on "Finding Factors Faster"?

Jim -- help me here, I can't find your 1979 reference. Here are the fastest factorizer articles by you that I have been able to find, not including the earlier ones:

• PPC Journal Vol. 5, No. 2 (March 1978). HP-67 program on page 22. Timing is stated to be 0.1043*sqrt(N)+2.5 seconds, for prime N.

• PPC Journal Vol. 5, No. 3 (April 1978). Article on pages 7-8 describes the HP-67 program in the previous issue as being a MOD 60 program, not MOD 210. In fact, the article says, "Thus, while a mod 210 factor finder is feasible on a '67, it is slower than a mod 30 due to increased overhead time." No new program was presented in this article; it was an overview of all prime factorizers published in PPC Journal up to that time.

• PPC Journal Vol. 8, No. 5 (July 1981). HP-41 program on page 19. Timing is stated to be 0.035*sqrt(N). It was the "fastest known factoring program" at that time. 100% standard HP-41 user language (no synthetics).