Factoring code

Support routines

• Integer Square Root
  • Integer Square Root (Fermat's method)
  • Integer Square Root (Halleck's method)
  • Integer Square Root (Legalize's speedup of Halleck's method)
• Modular addition X + Y (mod n)
• Modular multiplication X * Y (mod n)
  • Traditional Method
  • Halleck's Method
• Modular exponent X ^ Y (mod n)
• Greatest Common Denominator
• Extended Greatest Common Denominator

Factoring Methods

• Phi(n) overshoot
• Square root constraints
• Potential Function Methods
  • Relation N = (S-A)*(S+B) [Halleck's method]
    • Directly from relation
    • Cleaned up
  • Relation N = (Y-X)*(Y+X) [Fermat's method]
    • Directly from relation
    • Cleaned up
  • relation N = (Q-2X)*Q [Han's method]
    • Directly from relation
    • Cleaned up
    • Sped up by noting q is odd
  • relation N = (S-2*A)*(S+2*B) for some S between P and Q. [LeRoy's method]
    • Directly from relation
  • relation N = (S-A)*(S+A+C) [Bill's method]
    • Directly from relation
  • relation N = (S-A)*(S+A+2*D) [Nahaj's method]
    • Directly from relation
  • relation N = P*Q [John's method]
    • Directly from relation
    • Sped up by noteing p < sqrt(n)
  • relation 0 = XX-(D*D+2*S*D-R) [Finnish method]
    • Directory from relation
  • relation N = 2*Y*P-P*P [Anon's method]
    • Directly from relation
  • relation N = P*(P+2X) [Antihan's method]
    • Directly from relation

Go to ...

• John Halleck's Factoring page
• John Halleck's home page

This page is http://www.cc.utah.edu/~nahaj/factoring/code.html
This page was last modified on November 29th, 1999