Potential function methods of factoring integers

Notation rehash

• N = P*Q (P less than Q, P prime, and Q possibly prime)
• N = S*S + R (S is between P and Q, Usually the Integer Square Root)
• N = Y*Y - X*X
• N = (S-A)*(S+B)
• C = B-A
• C = 2 * D

Skimpy explanation

Potential function methods take a description of the factors of the form g(x,y) = f(x,y)*h(x,y) = N, f and h are descriptions of two factors.

f and h are both monotonic in each of the variables. g must be such that increasing one of x or y increases the function, and increasing the other decreases the function.

We compute what the effect of incrementing each variable is, and at each step we try to drive the value to zero.

When we succeed, then we use the values to compute the factors.

The algorithms themselves

• Relation N = (S-A)*(S+B) [Halleck's method] (Running time proportional to q-p)
  • Directly from relation
  • Cleaned up
• Relation N = (Y-X)*(Y+X) [Fermat's method] (Running time proportional to q) N must be odd
  • 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 noting p < sqrt(n)
• relation 0 = XX-(D*D+2*S*D-R) [Finnish method]
  • Directly 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/potential.html
© Copyright 2001 by John Halleck, All Rights Reserved
This page was last modified on January 18th, 2001