| How It Works | |
|---|---|
| (1) Let N be a composite number, defined as: where each p and q is prime and may be equal to any other p or q. Each factor is arbitrarily assigned to p or q. |
N = p1 · p2 · p3 · ... · pm · q1 · q2 · q3 · ... · qn |
| (2) If for N, we find u and v such that u2 ≡ v2 (mod N): | Then, u2 - v2 ≡ 0 (mod N) (u + v) · (u - v) ≡ 0 (mod N), and (u + v) · (u - v) = k1 · k2 · N for some integers 1 ≤ k1 < k2 |
| (3) From (1) and (2), | (u + v) · (u - v) = k1 · k2 · p1 · p2 · p3 · ... · pm · q1 · q2 · q3 · ... · qn |
| (4) If (u + v) [ or (u - v)] = k1 · k2, then (u - v) [or (u + v)] = N, and determination of u and v will not yield a useful result. If u ≡ ±v (mod N), then (u + v) and (u - v) ≡ 0 (mod N) and determination of u and v will not yield a useful result. |
|
| (5) If (u + v) = k1 · p1 · p2 · p3 · ... · pm, and (u - v) = k2 · q1 · q2 · q3 · ... · qn (or vice versa), then |
N ∤ (u + v) N ∤ (u - v) But gcd(u+v, N) = p1 · p2 · p3 ... · pm And gcd(u-v, N) = q1 · q2 · q3 ... · qn Which are factors of N |
| Algorithm Implementation | |
| Starting at the integer portion of √N, run through x0 = √N, x1 = √N+1, x2 = √N+2, ... | |
| For each, xi, calculate Q(xi) = xi2 - N | Then xi2 ≡ Q(xi) (mod N) By the Modular Multiplication Rule, xi2 (mod N) · xj2 (mod N) ≡ xi2 · xj2 ≡ Q(xi) · Q(xj) (mod N) |
| Define a factor base consisting of -1 and small primes up to a designated smoothing limit (F = {-1, 2, 3, 5, 7, 11 ...}) | |
| Factor each Q(xi) by each member of F: where Ri is the residual integer after all members of the factor base have been applied. |
Q(xi) = -1ai0 · 2ai1 · 3ai2 · 5ai3 · ... · Ri |
| Discard all Q(xi) where Ri > 1 Save each remaining {ai} as an exponent vector corresponding to xi, Q(xi) | |
| Find a subset, j, of Q(xi) where the sum of each exponent vector term is even. The product of those Q(xj), having all even exponents, is a perfect square | |
| We can now set u2 = [xj1 · xj2 · xj3 · ... ]2, and v2 = Q(xj1) · Q(xj2) · Q(xj3) · ... | |
| Solving for u and v, then (u+v) and (u-v), then gcd(u+v, N) and gcd(u-v, N) provides factors for N, which may or may not be trivial | |
| If the product of a subset of Q(x), Qi1 · Qi2 · Qi3 · ...
= Q2tot(x) is a square, then (xi1 · xi2 · xi3 · ...)2 = Q2tot(x) (mod N) | |