New test for Mersenne prime - Page 2

science_man_88 · 2011-05-19, 21:09

Quote:

Originally Posted by ATH

I don't use PARI but are you sure it can handle the large numbers? x is larger than (2ⁿ-1)². I used the GMP library.

pari should handle it as it's an extended arithmetic calculator but it might be that the memory I can use in 32 bit is too low.

science_man_88 · 2011-05-19, 22:14

Quote:

Originally Posted by ATH

I don't use PARI but are you sure it can handle the large numbers? x is larger than (2ⁿ-1)². I used the GMP library.

${(n-1)}{k^2}+{(n-2)}{k}$ if I did the math correct.

science_man_88 · 2011-05-19, 22:20

Quote:

Originally Posted by science_man_88

${(n-1)}{k^2}+{(n-2)}{k}$ if I did the math correct.

the exponent (x-1) is -1 mod k the base is -n+2 mod k , could we not use this to solve for n that work with this ? maybe the same modular arithmetic we used.

CRGreathouse · 2011-05-20, 01:40

Quote:

Originally Posted by ATH

I don't use PARI but are you sure it can handle the large numbers? x is larger than (2ⁿ-1)². I used the GMP library.

As I wrote here
http://rosettacode.org/wiki/Extreme_...lues#PARI.2FGP:
On a 64-bit machine, Pari t_REAL numbers have a maximum value of $2^{2^{61}}(1-\varepsilon)$ where ε is the machine epsilon at the selected precision.

So if x is about 4^n then PARI can handle n up to about 2e18.

ATH · 2011-05-20, 11:31

This conjecture is also true for exponents
19937,21701,23209,44497,86243,110503,132049,216091
corrensponding to Mersenne primes number 24 to 31. But I haven't tested all numbers up to 216091, only up to 18,000.

To summarize the conjecture:
M_p=2^p-1 is prime if: (M_p-p+2)^x-1 == 1 (mod M_p)
where x = M_p²*(p-1) - M_p*(p-2).

Is this conjecture interesting or just a rewriting of the LL test or is it false? I hope someone smarter than me read this :) To me it seems significant if it's proven true, since it's a "simple" modular exponentiation compared to LL test algorithm where you square and substract 2 each iteration.

How about the runtime of this test? x is of the order M_p², so it needs around M_p squarings same as the LL test?

TimSorbet · 2011-05-20, 11:49

I wrote straightforward implementations of both this and the LL test in C using GMP, and compared them to each other. The new test takes about 2.1 times as long as the LL. (the program is attached, if anyone wants to look at how I did it, make improvements, etc.) But I couldn't tell you if it were optimized, which would really be faster. If it really only needs about the same squarings as the LL test, as ATH suggested, it might be even faster than the LL because you don't need to subtract 2 on each iteration, you must have to do modular exponentiation.
Testing M11213 took 4.84 seconds using the LL, and 10.25 seconds using this new method. Testing M21701 took 25.76 seconds using LL, and 56.01 seconds using this new method.

As for its accuracy, it certainly seems to be correct from the tests you've done. At worst, I'd say it's a way to PRP test a Mersenne.
But a proof of it being true, whether as a 'rewording' of the LL or not, would be great!

R.D. Silverman · 2011-05-20, 12:27

Quote:

Originally Posted by ATH

This conjecture is also true for exponents
19937,21701,23209,44497,86243,110503,132049,216091
corrensponding to Mersenne primes number 24 to 31. But I haven't tested all numbers up to 216091, only up to 18,000.

To summarize the conjecture:
M_p=2^p-1 is prime if: (M_p-p+2)^x-1 == 1 (mod M_p)
where x = M_p²*(p-1) - M_p*(p-2).

Is this conjecture interesting or just a rewriting of the LL test or is it false? I hope someone smarter than me read this :) To me it seems significant if it's proven true, since it's a "simple" modular exponentiation compared to LL test algorithm where you square and substract 2 each iteration.

How about the runtime of this test? x is of the order M_p², so it needs around M_p squarings same as the LL test?

Sigh. Doesn't anyone here bother to reduce this 'conjecture' to something
simple, based on elementary number theory and elementary algebra?

(1) The exponent is ~ (M_p)^2 for doing essentially a PRP test. This is
TWICE the work for an LL test. (the number of squarings is double that
for LL)

(2) Hasn't anyone observed that this obscure value for x gives
that x-1 is a multiple of (M_p -1)? (!!!!!!!!!!) Put M_p = 2^p - 1,
and expand the expression for x-1. Now simplify.

Hasn't anyone observed that by
Fermat's little theorem a^z = 1 mod M_p whenever z is a multiple of
(M_p - 1)??? (and (a, M_p) == 1)??????

This so called 'new' conjecture simply amounts to saying that
a = (M_p - p + 2) is not a false witness for M_p. Of course
a^(x-1) = 1 mod M_p whenever M_p is prime and (a, M_p) = 1.
This is just Fermat's little theorem.

But it does so by creating this artificial exponent (x-1) that is TWICE AS LONG
AS NECESSARY to do a PRP test!

This is all elementary.

science_man_88 · 2011-05-20, 12:48

Quote:

Originally Posted by R.D. Silverman

Sigh. Doesn't anyone here bother to reduce this 'conjecture' to something
simple, based on elementary number theory and elementary algebra?

(1) The exponent is ~ (M_p)^2 for doing essentially a PRP test. This is
TWICE the work for an LL test. (the number of squarings is double that
for LL)

(2) Hasn't anyone observed that this obscure value for x gives
that x-1 is a multiple of (M_p -1)? (!!!!!!!!!!) Put M_p = 2^p - 1,
and expand the expression for x-1. Now simplify.

Hasn't anyone observed that by
Fermat's little theorem a^z = 1 mod M_p whenever z is a multiple of
(M_p - 1)??? (and (a, M_p) == 1)??????

This so called 'new' conjecture simply amounts to saying that
a = (M_p - p + 2) is not a false witness for M_p. Of course
a^(x-1) = 1 mod M_p whenever M_p is prime and (a, M_p) = 1.
This is just Fermat's little theorem.

But it does so by creating this artificial exponent (x-1) that is TWICE AS LONG
AS NECESSARY to do a PRP test!

This is all elementary.

2) no in fact I find using PARI that x is 0 mod $M_p-1$ ( so x-1 shouldn't also be).

R.D. Silverman · 2011-05-20, 13:13

Quote:

Originally Posted by science_man_88

2) no in fact I find using PARI that x is 0 mod $M_p-1$ ( so x-1 shouldn't also be).

I did it by hand. It is quite possible that I dropped a '-1'
term somewhere in doing the expansion. I can make transcription
errors as easily as anyone else.

However, just as a test, put p = 5, M_p = 31. M_p - 1 = 30.

Then x = 31^2 (5 - 1) - 31 (5 - 2) = 3751. This is definitely not
0 mod 30. It is the case, however, that x-1 = 3750 is a multiple of 30
(which is M_p - 1) as I stated before.

Further, if your claim is true, then something is [b] really[\b] weird/wrong.

If x = 0 mod (M_p - 1) then [working mod M_p] we have

x = k (M_p - 1) for some k, whence

a^(x-1) = a^( k(M_p -1) - 1)

= a^(k (M_p-1)) * a^-1

= 1 * a^-1 = 1/a mod M_p.

a = M_p - p + 2 and 1/a definitely isn't 1.

Recheck your calculations.

science_man_88 · 2011-05-20, 13:20

Quote:

Originally Posted by R.D. Silverman

I did it by hand. It is quite possible that I dropped a '-1'
term somewhere in doing the expansion. I can make transcription
errors as easily as anyone else.

However, just as a test, put p = 5, M_p = 31. M_p - 1 = 30.

Then x = 31^2 (5 - 1) - 31 (5 - 2) = 3751. This is definitely not
0 mod 30. It is the case, however, that x-1 = 3750 is a multiple of 30
(which is M_p - 1) as I stated before.

Further, if your claim is true, then something is [b] really[\b] weird/wrong.

If x = 0 mod (M_p - 1) then [working mod M_p] we have

x = k (M_p - 1) for some k, whence

a^(x-1) = a^( k(M_p -1) - 1)

= a^(k (M_p-1)) * a^-1

= 1 * a^-1 = 1/a mod M_p.

a = M_p - p + 2 and 1/a definitely isn't 1.

Recheck your calculations.

it might be my PARI :

Code:

(09:40)>Mp^2*(p-1) - Mp*(p-2)
%215 = (Mp^2 - Mp)*p + (-Mp^2 + 2*Mp)
(09:40)>%%(Mp-1)
%216 = 0
(10:12)>Mp^2*(p-1) - Mp*(p-2)
%227 = (Mp^2 - Mp)*p + (-Mp^2 + 2*Mp)
(10:12)>%%(Mp)
%228 = 0

I only see one case of this possible it's possible ( and quite likely I guess ) that I don't know what PARI does to get this it's probably with a variable at 0.

R.D. Silverman · 2011-05-20, 14:05

Quote:

Originally Posted by science_man_88

it might be my PARI :

Code:

(09:40)>Mp^2*(p-1) - Mp*(p-2)
%215 = (Mp^2 - Mp)*p + (-Mp^2 + 2*Mp)
(09:40)>%%(Mp-1)
%216 = 0
(10:12)>Mp^2*(p-1) - Mp*(p-2)
%227 = (Mp^2 - Mp)*p + (-Mp^2 + 2*Mp)
(10:12)>%%(Mp)
%228 = 0

I only see one case of this possible it's possible ( and quite likely I guess ) that I don't know what PARI does to get this it's probably with a variable at 0.

Something is WEIRD. I may be totally screwed up here, but I double
checked my arithmetic. I keep getting that x-1 is divisible by (M_p-1),
not that x is divisible by (M_p - 1).

Might we have a third party weigh in here?

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
(M48) NEW MERSENNE PRIME! LARGEST PRIME NUMBER DISCOVERED!	dabaichi	News	571	2020-10-26 11:02
Another way to PRP test Mersenne numbers	paulunderwood	Miscellaneous Math	18	2017-01-26 20:33
How do I test if it is a mersenne prime on GIMPS?	spkarra	Math	21	2015-01-23 18:13
another mersenne prime test	jocelynl	Math	8	2006-10-20 19:36
The 40th known Mersenne prime, 220996011-1 is not PRIME!	illman-q	Miscellaneous Math	33	2004-09-19 05:02

2011-05-20, 11:31	#16
ATH Einyen Dec 2003 Denmark 3²×383 Posts	This conjecture is also true for exponents 19937,21701,23209,44497,86243,110503,132049,216091 corrensponding to Mersenne primes number 24 to 31. But I haven't tested all numbers up to 216091, only up to 18,000. To summarize the conjecture: M_p=2^p-1 is prime if: (M_p-p+2)^x-1 == 1 (mod M_p) where x = M_p²(p-1) - M_p(p-2). Is this conjecture interesting or just a rewriting of the LL test or is it false? I hope someone smarter than me read this :) To me it seems significant if it's proven true, since it's a "simple" modular exponentiation compared to LL test algorithm where you square and substract 2 each iteration. How about the runtime of this test? x is of the order M_p², so it needs around M_p squarings same as the LL test?