HP 41C Pollard Brent Integer Factorization

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