A (new) old, (faster) slower mersenne-(primality) PRP test - Page 5

science_man_88 · 2014-04-14, 21:19

Quote:

Originally Posted by chalsall

Are you distantly related to Rick Mercer?

No, not to my knowledge. Okay sorry,What I meant was in my mind it is because it gets the bit length of the number you are squaring down by one.

paulunderwood · 2014-04-14, 21:58

Using boldi's test 3^((M+1)/2)==-3 (mod M), which is all squaring in left-right exponentiation, is it necessary to do an inverse FFT at each step? Or can we stay in FFT space for a couple or more steps?

tapion64 · 2014-04-14, 22:04

I believe the conjecture is false, or atleast requires some more grand effort to prove true, after working out the symbols. As it turns out, Mersenne primes also have (3/Mp) is equal to -1 when Mp is prime, so we have that if Mp is prime, the congruence holds in one direction.

If 3^(Mp-1)/2 = -1 mod Mp, then 3^(Mp-1) = 1 mod Mp, which implies order mod 3 is M-1 since order does not divide (Mp-1)/2. This would imply that Mp is either prime or a pseudoprime base 3. As someone pointed out, the converse of Fermat's little theorem is not generally true, but we're not quitters, so we use Lehmer's theorem that is true. It says that if the above condition holds, and for all primes q dividing Mp-1 we have 3^(Mp-1)/q != 1, then p is prime. Mp-1 = 2^p-2 = 2*(2^(p-1)-1), so we try using 2. by conjecture above, that's -1, so we're fine. But in order to prove the rest of this, we need to factor 2^(p-1)-1. We know that 3 divides this number for odd primes, but I doubt we can really know for sure that every other factor satisfies for Lehmer's theorem... It's possible, certainly, but I have no idea how to start proving it. The proof is already done here when dealing with Fermat numbers, as (2^(2^n)-1)+1 is a power of 2, and by the original assumption satisfies Lehmer's theorem.

To be more precise, if the conjecture is true, we have to prove there are no Mersenne numbers which are pseudoprimes of base 3. If we find even one counter example, it's false. Of course you might be able to modify it into a weaker statement that's true. But I feel like it's just not going to work out, the possible factors are too diverse.

science_man_88 · 2014-04-14, 22:25

Quote:

Originally Posted by tapion64

If 3^(Mp-1)/2 = -1 mod Mp, then 3^(Mp-1) = 1 mod Mp, which implies order mod 3 is M-1 since order does not divide (Mp-1)/2. This would imply that Mp is either prime or a pseudoprime base 3. As someone pointed out, the converse of Fermat's little theorem is not generally true, but we're not quitters, so we use Lehmer's theorem that is true. It says that if the above condition holds, and for all primes q dividing Mp-1 we have 3^(Mp-1)/q != 1, then p is prime. Mp-1 = 2^p-2 = 2*(2^(p-1)-1), so we try using 2. by conjecture above, that's -1, so we're fine. But in order to prove the rest of this, we need to factor 2^(p-1)-1. We know that 3 divides this number for odd primes, but I doubt we can really know for sure that every other factor satisfies for Lehmer's theorem... It's possible, certainly, but I have no idea how to start proving it. The proof is already done here when dealing with Fermat numbers, as (2^(2^n)-1)+1 is a power of 2, and by the original assumption satisfies Lehmer's theorem.

$2^{p-1}-1 = 2^{2x}-1$ which divisible by 2^x+1 and 2^x-1 for some value x, and so now can be reduced to factoring both.

tapion64 · 2014-04-14, 22:28

Quote:

Originally Posted by science_man_88

$2^{p-1}-1 = 2^{2x}-1$ which divisible by 2^x+1 and 2^x-1 for some value x, and so now can be reduced to factoring both.

Yeah, but how can we factor somewhat arbitrary numbers and prove those factors will never cause the Lehmer congruency to hold?

fivemack · 2014-04-14, 22:30

Quote:

Originally Posted by paulunderwood

Using boldi's test 3^((M+1)/2)==-3 (mod M), which is all squaring in left-right exponentiation, is it neccessay to do an inverse FFT at each step? Or can we stay in FFT space for a couple or more steps?

Yes, you still need to do an inverse FFT, because you have to propagate the carries to keep the signal values from getting too big for your FP precision. You might be able to do something heroic with the Chinese remainder theorem, but at that point you're not taking advantage of the floating point unit. If you want to do arithmetic modulo [150, 159, 207, 247]*2^42+1 then you could run 2^21 33-bit numbers and get to do two squarings before a carry propagation, but you can do better doing something less baroque.

science_man_88 · 2014-04-14, 22:34

Quote:

Originally Posted by tapion64

Yeah, but how can we factor somewhat arbitrary numbers and prove those factors will never cause the Lehmer congruency to hold?

we know the factors of a Mersenne number with a prime exponent are of form 2kp+1 for some value k and some exponent p. so if x is prime we can use that to our advantage.

tapion64 · 2014-04-14, 22:41

Quote:

Originally Posted by science_man_88

we know the factors of a Mersenne number with a prime exponent are of form 2kp+1 for some value k and some exponent p. so if x is prime we can use that to our advantage.

But we're not factoring Mp, we're factoring Mp-1, which is 2*(2^(p-1)-1), and the exponent there is no longer prime. Even so, we're not going to actually factor the number. We just need to show that none of its factors would cause Lehmer's congruence to fail. As far as I know, we haven't figured out how to determine if a number is or isn't a pseudoprime base a.

science_man_88 · 2014-04-14, 22:48

Quote:

Originally Posted by tapion64

But we're not factoring Mp, we're factoring Mp-1, which is 2*(2^(p-1)-1), and the exponent there is no longer composite. Even so, we're not going to actually factor the number. We just need to show that none of its factors would cause Lehmer's congruence to fail. As far as I know, we haven't figured out how to determine if a number is or isn't a pseudoprime base a.

Replace p with x, and you can then try to factor 2^x-1 if x is prime. If not you go back to factoring a composite exponent Mersenne until you can find prime exponent ones. Wait, are we using odd p to begin with ? if so it still holds that it goes down to 2^x+1 to 2^x-1 for some value x . Look, to be honest I'm not advanced.

chalsall · 2014-04-14, 23:00

Quote:

Originally Posted by science_man_88

Look, to be honest I'm not advanced.

I still think you're related to Rick Mercer. Is not everyone from Nova Scotia related to each other?

tapion64 · 2014-04-14, 23:10

No base-3 pseudo-prime divides a prime-exponent Mersenne number.

Conjecture B
As far as I know, I was the first to suggest this conjecture, via the Mersenne mailing list soon after it started.
Update (4/26/1997): Jon Grantham has sent a message to the mersenne@base.com mailing list with a counter-example based on some work of Peter Montgomery's. To quote part of his message:
Take n=193949641=3863*50207. n|2↑1931-1, and 1931 is prime. 3↑n=3 mod n, so it's a base 3 pseudoprime.

Found this on the net. So, I'm pretty sure that means the conjecture is false.
It would mean that the congruence 3^(M-1) = 1 mod M holds even though M is composite.
But M is really large and I don't think I can calculate that by hand >.> Maybe we can use
combo of Jacobi symbol and Legendre symbol. Anyways, pseudo primes are rare. But I'd want more speed up
than the algorithm gives us for a probabalistic test.

2014-04-14, 21:58	#46
paulunderwood Sep 2002 Database er0rr 3,739 Posts	Using boldi's test 3^((M+1)/2)==-3 (mod M), which is all squaring in left-right exponentiation, is it necessary to do an inverse FFT at each step? Or can we stay in FFT space for a couple or more steps? Last fiddled with by paulunderwood on 2014-04-14 at 22:25

2014-04-14, 22:04	#47
tapion64 Apr 2014 5×17 Posts	I believe the conjecture is false, or atleast requires some more grand effort to prove true, after working out the symbols. As it turns out, Mersenne primes also have (3/Mp) is equal to -1 when Mp is prime, so we have that if Mp is prime, the congruence holds in one direction. If 3^(Mp-1)/2 = -1 mod Mp, then 3^(Mp-1) = 1 mod Mp, which implies order mod 3 is M-1 since order does not divide (Mp-1)/2. This would imply that Mp is either prime or a pseudoprime base 3. As someone pointed out, the converse of Fermat's little theorem is not generally true, but we're not quitters, so we use Lehmer's theorem that is true. It says that if the above condition holds, and for all primes q dividing Mp-1 we have 3^(Mp-1)/q != 1, then p is prime. Mp-1 = 2^p-2 = 2(2^(p-1)-1), so we try using 2. by conjecture above, that's -1, so we're fine. But in order to prove the rest of this, we need to factor 2^(p-1)-1. We know that 3 divides this number for odd primes, but I doubt we can really know for sure that every other factor satisfies for Lehmer's theorem... It's possible, certainly, but I have no idea how to start proving it. The proof is already done here when dealing with Fermat numbers, as (2^(2^n)-1)+1 is a power of 2, and by the original assumption satisfies Lehmer's theorem. To be more precise, if the conjecture is true, we have to prove there are no Mersenne numbers which are pseudoprimes of base 3. If we find even one counter example, it's false. Of course you might be able to modify it into a weaker statement that's true. But I feel like it's just not going to work out, the possible factors are too diverse. Last fiddled with by tapion64 on 2014-04-14 at 22:26*

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Fastest software for Mersenne primality test?	JonathanM	Information & Answers	25	2020-06-16 02:47
New Mersenne primality test	Prime95	Miscellaneous Math	19	2014-08-23 04:18
LLT Cycles for Mersenne primality test: a draft	T.Rex	Math	1	2010-01-03 11:34
Mersenne Primality Test in Hardware	Unregistered	Information & Answers	4	2007-07-09 00:32
A primality test for Fermat numbers faster than Pépin's test ?	T.Rex	Math	0	2004-10-26 21:37

2014-04-14, 23:10	#55
tapion64 Apr 2014 5·17 Posts	No base-3 pseudo-prime divides a prime-exponent Mersenne number. Conjecture B As far as I know, I was the first to suggest this conjecture, via the Mersenne mailing list soon after it started. Update (4/26/1997): Jon Grantham has sent a message to the mersenne@base.com mailing list with a counter-example based on some work of Peter Montgomery's. To quote part of his message: Take n=193949641=3863*50207. n\|2↑1931-1, and 1931 is prime. 3↑n=3 mod n, so it's a base 3 pseudoprime. Found this on the net. So, I'm pretty sure that means the conjecture is false. It would mean that the congruence 3^(M-1) = 1 mod M holds even though M is composite. But M is really large and I don't think I can calculate that by hand >.> Maybe we can use combo of Jacobi symbol and Legendre symbol. Anyways, pseudo primes are rare. But I'd want more speed up than the algorithm gives us for a probabalistic test.