- Hello everyone

Over a year an a half ago I wondered how much improvement I could make

on Fermat factoring,

by using mod 8, 3, 5, 7, etc

for more quickly finding difference of squares equal to the number to

be factored.

Finally the algorithm for doing it came to me. I've written tentative

code, but it still has a bug in it.

In spite of this bug, I now realize that the screening by small modulii

does not help significantly.

To illustrate the process,

Suppose z = t^2 - s^2 .

If z = 1 mod 8, then t is in {1,3,5,7} mod 8 and s is in { 0,4} mod 8

If z = 3 mod 8, then t is in {2,6} mod 8 and s is in {1,3,5,7} mod 8

If z = 5 mod 8, then t is in {1,3,5,7} mod 8, and s is in {2,6} mod 8

If z = 7 mod 8, then t is in {0,4} mod 8, and s is in {1,3,5,7} mod 8.

If z = 1 mod 3, then t is in {1,2} mod 3 and s is in {0} mod 3

If z = 2 mod 3, then t is in {0} mod 3 and s is in {1,2} mod 3

If z = 1 mod 5, then t is in {0,1,4} mod 5 and s is in {0,2,3} mod 5

If z = 2 mod 5, then t is in {1,4} mod 5 and s is in {2,3} mod 5

If z = 3 mod 5, then t is in {2,3} mod 5 and s is in {1,4} mod 5

If z = 4 mod 5, then t is in {0,2,3} mod 5 and s is in {0,1,4} mod 5.

etc

z = t^2 - s^2 .

Given the number z to be factored, I found z mod p for each positive

prime p < 10000,

then made a bitmap table for permitted and nonpermitted values of t mod p,

and made a bitmap table for permitted and nonpermitted values of s mod p.

The calculation to make the 2 * 1229 bitmap tables took less than a minute.

As a preliminary, I made 1229 mod square root tables for each prime

modulus < 10000.

The time of calculation of the square root tables is included in that

"less than a minute" alluded to above.

I tested out my tentative program code on a product of two five digit

primes.

I haven't tried to time this sieve program on t values and s values in

comparison to other algorithms.

I just wanted to confirm whether or not this method would be timewise

exponential or sub exponential.

I'm almost persuaded that this screening method must be exponential,

and thus will not, in itself, provide

rapid factoring of large numbers.

This is in spite of using sieve methods for generating the mod sqrt

tables, and for generating the

bitmaps of permitted t values and permitted s values.

Perhaps I could speed it up a little bit by being more clever in my

sieve algorithms and in paying closer attention

to when I'm doing the same calculation more than once.

But, right now I don't feel it's worth effort to try.

I should go back to the textbooks for more inspiration on some of the

other factoring algorithms that have come to mind.

Kermit < kermit@... > - --- Kermit Rose <kermit@...> wrote:
> Hello everyone

I remember doing the same. I was sitting at an HPUX workstation at Nokia, so I

>

> Over a year an a half ago I wondered how much improvement I could make

> on Fermat factoring, by using mod 8, 3, 5, 7, etc

> for more quickly finding difference of squares equal to the number to

> be factored.

guess that was 6-7 years ago.

> Finally the algorithm for doing it came to me. I've written tentative

...

> code, but it still has a bug in it.

>

> In spite of this bug, I now realize that the screening by small modulii

> does not help significantly.

> I should go back to the textbooks for more inspiration on some of the

It's a constant factor speedup. See the 'Factoring with sieves' section in

> other factoring algorithms that have come to mind.

Knuth. Which is basically an accelerated Fermat. I'm convinced it's possible to

implement faster than how Knuth suggests, but again, that would only be another

small constant factor speedup.

Phil

() ASCII ribbon campaign () Hopeless ribbon campaign

/\ against HTML mail /\ against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]

____________________________________________________________________________________

Want to start your own business?

Learn how on Yahoo! Small Business.

http://smallbusiness.yahoo.com/r-index