mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2003-03-07, 23:44   #1
gbvalor
 
gbvalor's Avatar
 
Aug 2002

3×37 Posts
Default About trial factoring

Hi all,

It has been a hard week and now is too late in Europe, so forgive me if I write something wrong. Here you are ...

Is well know that for a prime p, if the Mersenne Number

Mp = 2^p - 1

is not prime and thus it has factors, they are in the form

F = k * q + 1

where q = 2 * p

I'm wonder whether we can take any advantage of this special form of
the Mersenne number factors in Trial factoring task, specially when
candidate factors are longer than 64 bits.

For trial factoring, once we have a candidate for factor passing the filters:

1) F=+1 or -1 (mod 8 )

2) F have no small factors

We have to make modular exponentiation (mod F). And see whether

2^p = 1 (mod F)

The most expensive task in the modular exponentiation is the modular
square, i. e. to compute

y = x * x (mod F)

If we write x < F in the form

x = a1 * q + a0, a0 < q, a1 < k (1)

it looks like a semi representation in base q . Note than a1 can be high
enough (a1 >> q).

We can write

x * x = (a1 * ((a1 * q) + 2 * a0 ))* q + a0 * a0; (2)

or

x * x = (a1 * a1 * q + 2 * a0 * a1 ) * q + a0 * a0; (3)



OTOH if we want to compute

(A * q) mod F = A * q mod ( k * q + 1) =

= r * q - c

where

r = A mod k
c = A / k (integer division)

i. e.

A = c * k + r

Usually, c can be computed fast in a FPU.

even more, we can see

A * q^2 mod F = (A * q) * q mod F =
= ((A * q) (mod F)) * q) (mod F) = (B * q) (mod F) =
= ((r0 * q - c0) * q) (mod F) =
= (r1 * q - c1) (4)

where A = c0 * k + r0
B = r0 * q - c0 = c1 * k + r1

Then to compute (3) we would need to perform three k-modulo and a
q-modulo plus some more work. Let's see and example. Suposse candidate
F having 70 bits, 25 bits for q and the remaining 45 to k.

What we need to do:

I) C = a1 * a1 * q^2 mod F

This requires
i ) 45 * 45 bits square x = (a1 * a1)
ii) compute c0 = int (x / k)
iii) compute r0 = x mod k
iv) compute B = r0 * q - c0 (70 bits arithmetic)
v) compute c1 = int (B / k)
vi) compute r1 = B mod k

II) D = 2 * a0 * a1 * q mod F
i) a 26 * 45 bits mul y = 2 * a0 * a1
ii) compute c2 = int (y / k)
iii) compute r2 = y mod k

III) a0 * a0
i) compute c3 = (a0 * a0 - c1 - c2) mod q
ii) compute r3 = int (a0 * a0 - c1 - c2) / q

IV) final
i) C = (r1 + r2 + r3) * q + c3
ii) normalization


Is a long list of things to do, but I don't know if is a lot of
work compared with multiprecision arithmetic we would make other way
The proposed scheme only uses modular arithmetic for lengths where
there fast and optimized algorithms.

Is this a cracy or wrong idea?. May be.

Guillermo Ballester Valor
gbvalor is offline   Reply With Quote
Old 2003-03-08, 01:34   #2
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×599 Posts
Default Re: About trial factoring

Quote:
Originally Posted by gbvalor
It has been a hard week and now is too late in Europe
Oh, not at all -- it's never too late in Europe. :)

Quote:
Is well know that for a prime p, if the Mersenne Number

Mp = 2^p - 1

is not prime and thus it has factors, they are in the form

F = k * q + 1

where q = 2 * p

I'm wonder whether we can take any advantage of this special form of
the Mersenne number factors in Trial factoring
Yes, Prime95 trial factoring has been taking advantage of that property since the very beginning.

Quote:
For trial factoring, once we have a candidate for factor passing the filters:

1) F=+1 or -1 (mod 8 )
Among other shortcuts, Prime95 trial factoring considers only the 16 congruence classes mod 120 (+-1, +-7, +-17, +-23, +-31, +-41, +-47, +-49) that might contain prime Mersenne factors. Thus it skips fourteen of the mod 120 congruence classes (+-9, +-15, +-25, +-33, +-39, +-55, and +-57) which satisfy +-1 mod 8 but are never prime.

Going to mod 840 congruence classes would enable also easily skipping all multiples of 7, but I presume George analyzed that long ago and found it not worth the extra complication compared to the cost of eliminating multiples of 7 in other steps.
cheesehead is offline   Reply With Quote
Old 2003-03-08, 07:42   #3
gbvalor
 
gbvalor's Avatar
 
Aug 2002

1578 Posts
Default

Hi,

Yes, I know this previous sieve work that all trial factoring code has to do. And in fact, is a great advantage the form of the factors.

But what I meant, sorry if I not explained well, is try to use this form in the modular exponentiation we have to do with the few candidates we still have after sieve work, when the size is over 64 bits .

Guillermo.
gbvalor is offline   Reply With Quote
Old 2003-05-22, 01:37   #4
Maybeso
 
Maybeso's Avatar
 
Aug 2002
Portland, OR USA

2·137 Posts
Default

Quote:
Originally Posted by gbvalor
But what I meant, sorry if I not explained well, is try to use this form in the modular exponentiation we have to do with the few candidates we still have after sieve work, when the size is over 64 bits .
Ah, I see now.

When the candidate factor F is over 64 bits, you want to use the method described in your first post to break it into several operations of < 64 bits.

I think the question you want is:
Is your method faster than [sp] karisuba multiplication (or other), plus a size*2 bit mod.

You'll want to compare your method for factor sizes of 64, <128, <192 bits, ... to see if it beats the others at that size range.

If you could code a function gbv(m, f) that uses your method to calculate 2^m - 1 (mod f), and someone codes it using several other big number methods, then we could run a time trial and see.
Any takers?

Bruce
Maybeso is offline   Reply With Quote
Old 2003-05-22, 02:04   #5
Maybeso
 
Maybeso's Avatar
 
Aug 2002
Portland, OR USA

11216 Posts
Default Re: About trial factoring

Quote:
Originally Posted by cheesehead
Among other shortcuts, Prime95 trial factoring considers only the 16 congruence classes mod 120 (+-1, +-7, +-17, +-23, +-31, +-41, +-47, +-49) that might contain prime Mersenne factors. Thus it skips fourteen of the mod 120 congruence classes (+-9, +-15, +-25, +-33, +-39, +-55, and +-57) which satisfy +-1 mod 8 but are never prime.
For a long time now, I've wanted to adapt the Atkins algorithm to generate primes in those 16 congruence classes using a single binary quadratic form. One obstacle for me was c is not my first language, so dealing with make files, etc. is a pain. Plus, to do it right, I wanted to incorporate one of the large number libraries.

I finally reduced my goal to writing a simple one that works, and wrote it as an html form using javascript. Now, someone can easily convert my source to c, mesh it with one of the libraries, and we'll be in business.

After reading the info on Trial Factoring, I suspect that this won't be usefull with the methods Prime95 uses to store and sieve candidate factors - Since each candidate is separated by at least 2*p.

But if anyone is interested, I can email it; or post it here as an attachment; or upload it to someones server and post a link.

Bruce
Maybeso is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Trial Factoring on AMD/ATI GPU's? Stargate38 GPU Computing 9 2018-08-31 07:58
What is Trial Factoring? Unregistered Information & Answers 5 2012-08-02 03:47
How much Trial Factoring to do? odin Software 4 2010-08-08 20:23
How far to do trial factoring S485122 PrimeNet 1 2007-09-06 00:52
How to only do Trial Factoring? michael Software 23 2004-01-06 08:54

All times are UTC. The time now is 03:07.

Sun Oct 25 03:07:58 UTC 2020 up 45 days, 18 mins, 0 users, load averages: 2.01, 2.07, 1.96

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.