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

• Previous message: Craig Feinstein: "Re: factoring integers on a classical computer in polynomial-time"
• In reply to: Craig Feinstein: "factoring integers on a classical computer in polynomial-time"
• Next in thread: Dik T. Winter: "Re: factoring integers on a classical computer in polynomial-time"
• Reply: Dik T. Winter: "Re: factoring integers on a classical computer in polynomial-time"
• Reply: Pubkeybreaker: "Re: factoring integers on a classical computer in polynomial-time"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

Date: 24 Mar 2005 13:02:37 -0800

Craig Feinstein wrote:
> 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

In order to settle the debate, would anyone like to try to code this up
in a computer language like C++ and run it lots of times, so that there
can be no debate as to whether it works or not?

Remember that step 2) requires finding a solution in which 2^n*alpha +
a != 1 (mod 2^{n+1}) and 2^n*beta + b != 1 (mod 2^{n+1}) whenever it is
possible to do such (i.e., whenever such a solution exists and has not
been rejected by step 4)), in order to prevent the algorithm from
outputting trivial factors when N is composite. If you don't code this
part up correctly, then the algorithm might not work and output trivial
factors, as we saw in earlier posts.

Craig

• Previous message: Craig Feinstein: "Re: factoring integers on a classical computer in polynomial-time"
• In reply to: Craig Feinstein: "factoring integers on a classical computer in polynomial-time"
• Next in thread: Dik T. Winter: "Re: factoring integers on a classical computer in polynomial-time"
• Reply: Dik T. Winter: "Re: factoring integers on a classical computer in polynomial-time"
• Reply: Pubkeybreaker: "Re: factoring integers on a classical computer in polynomial-time"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]