20040828, 22:49  #1 
May 2003
2^{5}×3 Posts 
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) ? 
20040829, 14:33  #2 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
The answer to your "little" question is Fermat's "little" theorem. It states that if p is a prime, then
a^(p1) == 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 
20040829, 16:58  #3 
May 2003
96_{10} Posts 
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. 
20040829, 21:24  #4  
Jun 2003
2×2,683 Posts 
Quote:


20040829, 21:50  #5 
May 2003
2^{5}·3 Posts 
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 ?

20040830, 01:00  #6 
Jun 2003
1010011110110_{2} Posts 
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. 
20040830, 18:15  #7  
Nov 2003
2^{2}×5×373 Posts 
Quote:
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. 

20050413, 00:52  #8 
Mar 2003
New Zealand
485_{16} Posts 
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? 
20050413, 01:10  #9 
"William"
May 2003
New Haven
4503_{8} Posts 
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 
20050413, 10:52  #10  
Mar 2005
Poland
100011_{2} Posts 
Quote:
Last fiddled with by Washuu on 20050413 at 10:56 

20050413, 12:06  #11 
Aug 2002
Buenos Aires, Argentina
1,447 Posts 
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 200digit 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 200digit strong pseudoprime (10^199+153) and according to the applet it took 4113428 modular multiplications to prove it is prime using APRTCLE. So now you can figure it out which method is faster. 