factoring integers on a classical computer in polynomial-time

From: Craig Feinstein (cafeinst_at_msn.com)
Date: 03/24/05 

Date: 24 Mar 2005 08:38:09 -0800

The algorithm that we present for factoring integers on a classical
computer in polynomial-time is so simple that any mathematics
undergraduate can understand how it works just by reading its code and
trying it out on a few cases. No detailed explanation is necessary, as
this would only complicate things.

Input: An odd positive integer N.

1) Let a=b=1 and n=1.

2) Solve N = (2^n*alpha + a)(2^n*beta + b) (mod 2^{n+1}) for alpha,
beta in {0,1}, if possible a solution in which 2^n*alpha + a != 1 (mod
2^{n+1}) and 2^n*beta + b != 1 (mod 2^{n+1}).

3) If N=(2^n*alpha + a)(2^n*beta + b), then output these factors of N
and stop.

4) If N<(2^n*alpha + a)(2^n*beta + b), then goto step 2) to find
a different solution for alpha, beta in {0,1}.

5) Let a:= 2^n*alpha + a and b:= 2^n*beta + b.

6) Let n:= n+1 and goto step 2).

Happy Purim,
Craig Feinstein