Little Question

Axel Fox · 2004-08-28, 22:49

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) ?

akruppa · 2004-08-29, 14:33

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

Axel Fox · 2004-08-29, 16:58

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.

axn · 2004-08-29, 21:24

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.

Axel Fox · 2004-08-29, 21:50

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 ?

axn · 2004-08-30, 01:00

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.

R.D. Silverman · 2004-08-30, 18:15

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.

geoff · 2005-04-13, 00:52

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?

wblipp · 2005-04-13, 01:10

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

Washuu · 2005-04-13, 10:52

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?

alpertron · 2005-04-13, 12:06

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.

2004-08-28, 22:49	#1
Axel Fox May 2003 2⁵×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 96₁₀ 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:50	#5
Axel Fox May 2003 2⁵·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 ?

2004-08-30, 01:00	#6
axn Jun 2003 1010011110110₂ 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.

2005-04-13, 00:52	#8
geoff Mar 2003 New Zealand 485₁₆ 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 4503₈ 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, 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.