Re: factoring integers on a classical computer in polynomial-time

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

Date: 26 Mar 2005 19:30:11 -0800

Please excuse me for being wrong before. As we saw, *** Winter
presented a case N=255 for which the algorithm could not work.

The algorithm that I originally presented was based on the theorem that
when ab=N (mod 2^n), we get the following for some integers alpha,
beta:

(alpha*2^n + a)(beta*2^n + b)=N (mod 2^{n+1}).

In the algorithm that I presented, I restricted alpha, beta to {0,1}.
Perhaps this is the problem. Perhaps I should have had less restriction
on alpha, beta and said that they should be in {-1,0,1}. That way, it
is possible to prevent the expression on the left-hand-side from
getting too large, as we saw in *** Winter's example for N=255.

Consider the following modification.

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 {-1,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 0<(2^n*alpha + a)(2^n*beta + b)< N is false, then goto step 2) to
find a different solution for alpha, beta in {-1,0,1}.

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

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

Would anyone like to show when this algorithm fails (if indeed this is
the case) or code it up to show that it works?

Craig

Quantcast