HP 41C Pollard Brent Integer Factorization

07042014, 07:07 PM
Post: #1




HP 41C Pollard Brent Integer Factorization
I don't know if anyone did this in the dark ages, but here's my try at this factorizing method.
POBR has 2 subprogrammes, 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 

07052014, 09:11 PM
Post: #2




RE: HP 41C Pollard Brent Integer Factorization
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.
Also, POBR never seems to finish with even moderatesized inputs, such as 991*997. Is this expected, or evidence of a bug? (I doublechecked to be sure that I keyed your programs in correctly.) <0ɸ0> Joe 

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? 

07062014, 06:55 AM
Post: #4




RE: HP 41C Pollard Brent Integer Factorization
(07062014 05:41 AM)Gerald H Wrote:(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. 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. 

07072014, 05:55 AM
Post: #5




RE: HP 41C Pollard Brent Integer Factorization
(07062014 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. <0ɸ0> Joe 

07072014, 06:04 AM
Post: #6




RE: HP 41C Pollard Brent Integer Factorization
A modulo 210 brute force factoring on the HP67 took 0.1042*sqrt(x) seconds in 1979. The HP41 averaged 3 times that speed. So your example would take around 58 minutes. (CF "Finding Factors Faster", PPC Journal, midCretaceous epoch, by some old phart)


07072014, 12:02 PM
Post: #7




RE: HP 41C Pollard Brent Integer Factorization
(07072014 06:04 AM)Jim Horn Wrote: A modulo 210 brute force factoring on the HP67 took 0.1042*sqrt(x) seconds in 1979. The HP41 averaged 3 times that speed. So your example would take around 58 minutes. (CF "Finding Factors Faster", PPC Journal, midCretaceous 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! <0ɸ0> Joe 

07072014, 12:27 PM
Post: #8




RE: HP 41C Pollard Brent Integer Factorization
(07072014 12:02 PM)Joe Horn Wrote:(07072014 06:04 AM)Jim Horn Wrote: A modulo 210 brute force factoring on the HP67 took 0.1042*sqrt(x) seconds in 1979. The HP41 averaged 3 times that speed. So your example would take around 58 minutes. (CF "Finding Factors Faster", PPC Journal, midCretaceous epoch, by some old phart) 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. 

07082014, 06:20 AM
Post: #9




RE: HP 41C Pollard Brent Integer Factorization
(07072014 12:27 PM)Gerald H Wrote: Is the NP programme written in a lower level language? No. 100% standard HP41 user language, not even any synthetics. Listing can be found on page 347 of the PPC ROM User's Manual. (07072014 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). HP67 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 78 describes the HP67 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). HP41 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 HP41 user language (no synthetics). <0ɸ0> Joe 

« Next Oldest  Next Newest »

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