Expand Messages
• This type of division runs much faster than the usual method and may have made it a contender in 1993 for the swiftest factoring method widely available. To
Message 1 of 3 , May 4, 2007
This type of division runs much faster than the usual method
and may have made it a contender in 1993 for the swiftest
factoring method widely available.

To illustrate:

Starting with N = 1372864271 find the smallest 48 number pairs
(a,b) such (N - a*b) mod 210 = 0. These are the starting points
for the rest of the calculations.

Suppose you have come upon (41,61). Take the sqrt(N)/210 = 176,
then find 176 * 210 + 41 = 37001 and 177 * 210 + 61 = 37231.
Next find N - 37001 * 37231 = -2246.

Let X = 37001, Y = 37231, Z = -2246.
The main loop of the method will be:

Repeat
Repeat
y := y + 210;
z := Z + X;
Until Z >= 0;
X := X - 210;
Z := Z - y;
Until Z <= 0;

Z = 0 at X = 20411, y = 67261 and X * Y = N.
• ... Probably not. ... Come upon ? ... That is not the main loop, the main loop would contain the procedure by which you come upon the pair (41,61), and
Message 2 of 3 , May 4, 2007
--- aldrich617 <aldrich617@...> wrote:
> This type of division runs much faster than the usual method
> and may have made it a contender in 1993 for the swiftest
> factoring method widely available.

Probably not.

> To illustrate:
>
> Starting with N = 1372864271 find the smallest 48 number pairs
> (a,b) such (N - a*b) mod 210 = 0. These are the starting points
> for the rest of the calculations.
>
> Suppose you have come upon (41,61).

'Come upon'?

> Take the sqrt(N)/210 = 176,
> then find 176 * 210 + 41 = 37001 and 177 * 210 + 61 = 37231.
> Next find N - 37001 * 37231 = -2246.
>
> Let X = 37001, Y = 37231, Z = -2246.
> The main loop of the method will be:
>
> Repeat
> Repeat
> y := y + 210;
> z := Z + X;
> Until Z >= 0;
> X := X - 210;
> Z := Z - y;
> Until Z <= 0;

That is not the main loop, the main loop would contain the procedure by which
you 'come upon' the pair (41,61), and would run what you have got there up to
48 times for each of the pairs that it 'comes upon'.

Here's a faster method to factor 1372864271:

First, come upon the value 20411.
Then perform the following
if(1372864271%20411==0) { output(20411," ",1372864271/20411); }
else { output("FLT is false"); }

Phil

() ASCII ribbon campaign () Hopeless ribbon campaign
/\ against HTML mail /\ against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]

__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com
• ... 1993, widely available ? I m looking at my copy of Riesel s Prime Numbers and Computer Methods for Factorization -- I have the second edition, which was
Message 3 of 3 , May 4, 2007
aldrich617 wrote:
> This type of division runs much faster than the usual method
> and may have made it a contender in 1993 for the swiftest
> factoring method widely available.
>

1993, "widely available"?

I'm looking at my copy of Riesel's "Prime Numbers and Computer
Methods for Factorization" -- I have the second edition, which
was published in 1994.

It discusses a bunch of methods which are generally much
faster than the method you mention. Pollard's rho algorithm
comes to mind as one which is *easier to implement* than the
method you describe, probably faster 99% of the time, and
which was invented in 1975. Brent's variant which improved
the performance was published in 1980.