# 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)
- Relation N = (Y-X)*(Y+X) [Fermat's method] (Running time proportional to q) N must be odd
- relation N = (Q-2X)*Q [Han's method]
- relation N = (S-2*A)*(S+2*B) for some S between P and Q. [LeRoy's method]
- relation N = (S-A)*(S+A+C) [Bill's method]
- relation N = (S-A)*(S+A+2*D) [Nahaj's method]
- relation N = P*Q [John's method]
- relation 0 = XX-(D*D+2*S*D-R) [Finnish method]
- relation N = 2*Y*P-P*P [Anon's method]
- relation N = P*(P+2X) [Antihan's method]

# Go to ...

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