## Using small moduli to filter in Fermat factoring

Expand Messages
• 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
Message 1 of 2 , Nov 10, 2006
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@... >
• ... I remember doing the same. I was sitting at an HPUX workstation at Nokia, so I guess that was 6-7 years ago. ... It s a constant factor speedup. See the
Message 2 of 2 , Nov 10, 2006
--- Kermit Rose <kermit@...> wrote:
> 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.

I remember doing the same. I was sitting at an HPUX workstation at Nokia, so I
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
> other factoring algorithms that have come to mind.

It's a constant factor speedup. See the 'Factoring with sieves' section in
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]

____________________________________________________________________________________