 mersenneforum.org Little Question
 Register FAQ Search Today's Posts Mark Forums Read  2004-08-28, 22:49 #1 Axel Fox   May 2003 25×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) ?   2004-08-29, 14:33 #2 akruppa   "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^(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   2004-08-29, 16:58 #3 Axel Fox   May 2003 1408 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.    2004-08-29, 21:24   #4
axn

Jun 2003

2×2,683 Posts 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.   2004-08-29, 21:50 #5 Axel Fox   May 2003 11000002 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 ?   2004-08-30, 01:00 #6 axn   Jun 2003 2·2,683 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.    2004-08-30, 18:15   #7
R.D. Silverman

Nov 2003

746010 Posts 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.   2005-04-13, 00:52 #8 geoff   Mar 2003 New Zealand 115710 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?   2005-04-13, 01:10 #9 wblipp   "William" May 2003 New Haven 45038 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   2005-04-13, 10:52   #10
Washuu

Mar 2005
Poland

438 Posts 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   2005-04-13, 12:06 #11 alpertron   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 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.   Thread Tools Show Printable Version Email this Page

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

Fri May 27 15:03:57 UTC 2022 up 43 days, 13:05, 1 user, load averages: 1.76, 1.75, 1.72