- 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. - --- aldrich617 <aldrich617@...> wrote:
> This type of division runs much faster than the usual method

Probably not.

> and may have made it a contender in 1993 for the swiftest

> factoring method widely available.

> To illustrate:

'Come upon'?

>

> 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,

That is not the main loop, the main loop would contain the procedure by which

> 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;

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 - aldrich617 wrote:
> This type of division runs much faster than the usual method

1993, "widely available"?

> and may have made it a contender in 1993 for the swiftest

> factoring method 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.

Your number factors on my laptop in about 2 milliseconds using

the example implementation of Brent's variant which comes with

PARI/GP.

Jack