mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2004-08-28, 22:49   #1
Axel Fox
 
Axel Fox's Avatar
 
May 2003

25×3 Posts
Default Little Question

In the lists of not completely factored Mersenne numbers, how do you know that the remaining cofactor is composite ?

So, what I'm asking is actually this : if I were to find a new factor (of the Mersenne numbers and since it's a new one, also a factor the the composite cofactor), how would I know that the new remaining cofactor is composite or prime (that there are more factors to be found or that it is now completely factored) ?
Axel Fox is offline   Reply With Quote
Old 2004-08-29, 14:33   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

25×7×11 Posts
Default

The answer to your "little" question is Fermat's "little" theorem. It states that if p is a prime, then

a^(p-1) == 1 (mod p)

for every a that is coprime to p. If p is not a prime, then usually most choices of a will result in a different value than 1 occurring, thus giving away the compositeness of a. Some numbers (Carmichael numbes) are composite but hard to detect with Fermat's test, but there are better (so called strong) probable primality tests. A good source of info is Chris Caldwell's prime pages, particularly the section on finding primes and proving primality.

The probable primality tests cannot prove primality (unless assuming GRH holds), only compositeness. But in practice they err so rarely that passing a few tests to different bases a establishes the primality of the number in question beyond reasonable doubt. Caldwell's page describes methods to mathematically prove primality, too, but that is much harder than just running a few probable prime tests.

Alex
akruppa is offline   Reply With Quote
Old 2004-08-29, 16:58   #3
Axel Fox
 
Axel Fox's Avatar
 
May 2003

9610 Posts
Default

Oh ok, thanks.

I am familiar with some PRP Tests, but I assumed that since they don't work for Mersenne numbers (otherwise we would use them to prove a lot of numbers composite before doing the LL Test), the also didn't work for their factors. But I guess I was wrong and they do work then.

Thanks for enlightening me.
Axel Fox is offline   Reply With Quote
Old 2004-08-29, 21:24   #4
axn
 
axn's Avatar
 
Jun 2003

23·19·31 Posts
Default

Quote:
Originally Posted by Axel Fox
but I assumed that since they don't work for Mersenne numbers (otherwise we would use them to prove a lot of numbers composite before doing the LL Test)
PRP works for all numbers - including Mersenne numbers. The reason it is not used is that, it takes almost exactly the same amount of computation for LL as well as PRP -- and, whereas a PRP gives you a "maybe" prime/"definitely" composite answer, LL-test gives you a "definitely" prime/"definitely" composite answer.
axn is offline   Reply With Quote
Old 2004-08-29, 21:50   #5
Axel Fox
 
Axel Fox's Avatar
 
May 2003

25·3 Posts
Default

Oh, IC, but then how do you know that the resulting cofactor is composite ? It seems to me that if you find a factor of a Mersenne number, it always a relatively small number (compared to the Mersenne number itself). This would make the resulting cofactor just a little bit small, which means it would take a long time to check that the cofactor is prime or composite ? So do they actually do a test that takes as long as a LL test on all these Cofactors ?
Axel Fox is offline   Reply With Quote
Old 2004-08-30, 01:00   #6
axn
 
axn's Avatar
 
Jun 2003

23×19×31 Posts
Default

I guess (this is a guess only), for small mersenne numbers (and hence small cofactors), you'll actually do the PRP (which takes just seconds to do). For really big Mersennes, I don't think anybody actually bothers to compute the cofactor, let alone check if they are composite. You kind of assume that that the number is not fully factored.

AFAIK, the current tables of factorization go up to about n = 1000.
axn is offline   Reply With Quote
Old 2004-08-30, 18:15   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1C4016 Posts
Thumbs up

Quote:
Originally Posted by Axel Fox
In the lists of not completely factored Mersenne numbers, how do you know that the remaining cofactor is composite ?

So, what I'm asking is actually this : if I were to find a new factor (of the Mersenne numbers and since it's a new one, also a factor the the composite cofactor), how would I know that the new remaining cofactor is composite or prime (that there are more factors to be found or that it is now completely factored) ?
"how would I know that the new remaining cofactor is composite or prime"

You know this because every integer > 1 is either composite or prime. There
are no other choices.

I think you meant to ask:

"how would I know whether the new remaining cofactor is composite or prime"


And the answer to this obvious: you test the cofactor for primality.
Of course any test is now a prp test, rather than deterministic.

Since the main purpose of GIMPS is to find Mersenne primes, noone
bothers to check primality of a cofactor when a small factor is found.
R.D. Silverman is offline   Reply With Quote
Old 2005-04-13, 00:52   #8
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13·89 Posts
Default

Who actually does the primality proof for the probable prime cofactors for the Cuningham project, and does this take significant effort, say for a 200 digit prp?

I am trying to prove the primality of the prp cofactors I have found sofar, and I wondered if doing this for new factors before I report them would be worthwhile?
geoff is offline   Reply With Quote
Old 2005-04-13, 01:10   #9
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

22·32·5·13 Posts
Default

There are lots of choices that will prove primes of that size quickly. I think the most convenient is to paste it into Dario Alpern's Java applet at

http://www.alpertron.com.ar/ECM.HTM
wblipp is offline   Reply With Quote
Old 2005-04-13, 10:52   #10
Washuu
 
Mar 2005
Poland

2216 Posts
Default

Quote:
Originally Posted by wblipp
There are lots of choices that will prove primes of that size quickly. I think the most convenient is to paste it into Dario Alpern's Java applet at

http://www.alpertron.com.ar/ECM.HTM
hmmm, but take for example number 394875391875093847503924230984230947133. Mentioned applet knows in less than second that this is composite, and 39487539187509384750392423098423094713333333333333 is prime, but applying Fermat Little Theorem would be much slower, because it has expponential running time, am I wrong?

Last fiddled with by Washuu on 2005-04-13 at 10:56
Washuu is offline   Reply With Quote
Old 2005-04-13, 12:06   #11
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

133310 Posts
Default

Applying the Fermat Theorem is much faster. The number of modular multiplication is less than two times the number of bits of the number.

For example for a 200-digit number the number of bits is about 665, so the number of modular multiplications is less than 1330 (in average is about 1000 modular multiplication, and if windowing methods are used you will need about 800 modular multiplications).

I entered in my applet the expression n(10^199) which is the first 200-digit strong pseudoprime (10^199+153) and according to the applet it took 4113428 modular multiplications to prove it is prime using APRT-CLE.

So now you can figure it out which method is faster.
alpertron is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 18:38.

Sat Oct 24 18:38:15 UTC 2020 up 44 days, 15:49, 0 users, load averages: 1.97, 2.02, 2.00

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.