HP Forums
HP 41C: Fermat Factorization - Printable Version

+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Software Libraries (/forum-10.html)
+--- Forum: HP-41C Software Library (/forum-11.html)
+--- Thread: HP 41C: Fermat Factorization (/thread-1801.html)



HP 41C: Fermat Factorization - Gerald H - 07-08-2014 02:06 PM

Fermat's factorization method is particularly good for finding large factors of a number, & very poor at finding small factors.

For example, for 608,391 (=3^4*7*29*37) the programme finds 777 & 783 almost instantaneously.

Consequently the method is most efficient in dealing with the "difficult" case of a composite number having two large prime factors.

The number 8616460799 is factorized in 695 s.

1. LBL “FERM”
2. STO 00
3. SQRT
4. INT
5. RCL X
6. RCL Y
7. +
8. 1
9. STO T
10. +
11. STO Z
12. RDN
13. X^2
14. RCL 00
15. –
16. LBL 00
17. X=0?
18. GTO 01
19. RCL Y
20. +
21. 2
22. ST+ Z
23. RDN
24. LBL 02
25. RCL Z
26. –
27. 2
28. ST+ T
29. RDN
30. X>0?
31. GTO 02
32. GTO 00
33. LBL 01
34. RDN
35. X<>Y
36. –
37. 2
38. /
39. RCL 00
40. RCL Y
41. /
42. END


RE: HP 41C: Fermat Factorization - Dwight Sturrock - 07-27-2014 01:41 AM

Adapted for the HP15C /LE :

1. LBL A
2. STO 0
3. SQRT
4. INT
5. ENTER
6. ENTER
7. +
8. 1
9. STO 4
10. +
11. STO 3
12. RDN
13. X^2
14. RCL 0
15. -
16. LBL 0
17. X=0
18. GTO 1
19. RCL 3
20. +
21. 2
22. STO +3
23. RDN
24. LBL 2
25. RCL 4
26. -
27. 2
28. STO +4
29. RDN
30. TEST 1 (X>0)
31. GTO 2
32. GTO 0
33. LBL 1
34. RCL 3
35. RCL 4
36. -
37. 2
38. /
39. ENTER
40. ENTER
41. RCL 0
42. X<>Y
43. /
44. RTN


RE: HP 41C: Fermat Factorization - Ángel Martin - 07-29-2014 06:13 PM

(07-27-2014 11:01 PM)Geir Isene Wrote:  Is this method made available as MCODE in one of Angel Martin's modules?

Not that I'm aware (and I guess I should know it :-) - I used the MCODE PRIME? function as the basis of the factorization - darn fast if you must know.