HP 41C: Fermat Factorization

[Gerald H]

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

[Dwight Sturrock]

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

[Ángel Martin]

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