New test for Mersenne prime - Page 3

science_man_88 · 2011-05-20, 14:11

Quote:

Originally Posted by R.D. Silverman

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?

yeah I'm confused but mostly because I don't see the math of the (Mp-1) part I see how x is easily 0 mod Mp ( both terms use Mp).

science_man_88 · 2011-05-20, 14:28

Code:

(11:16)>(-Mp^2 + 2*Mp)%(Mp^2-Mp)
%232 = Mp

this proves my early PARI incorrect it seems ( being 0 mod Mp and 0 mod Mp-1 leads to, 0 mod (Mp^2-Mp)) the first term according to previous PARI was (Mp^2-Mp)*p easily 0 mod (Mp^2-Mp). the second appears to show Mp mod that number making the whole equation Mp mod that number but if I subtract 1 ( to give x-1) I get Mp-1 which lines up with you. I may have to virus check my computer now. or figure out a way to get PARI to stop giving bad results it seems.

science_man_88 · 2011-05-20, 15:47

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.

after the virus scan:

Code:

(12:44)>Mp^2*(p-1) - Mp*(p-2)
%1 = (p - 1)*Mp^2 + (-p + 2)*Mp
(12:44)>%%(Mp-1)
%2 = 1
(12:45)>Mp^2*(p-1) - Mp*(p-2)
%3 = (p - 1)*Mp^2 + (-p + 2)*Mp
(12:45)>%%(Mp)
%4 = 0
(12:45)>

a different simplification ?

science_man_88 · 2011-05-20, 16:11

Quote:

Originally Posted by science_man_88

after the virus scan:

Code:

(12:44)>Mp^2*(p-1) - Mp*(p-2)
%1 = (p - 1)*Mp^2 + (-p + 2)*Mp
(12:44)>%%(Mp-1)
%2 = 1
(12:45)>Mp^2*(p-1) - Mp*(p-2)
%3 = (p - 1)*Mp^2 + (-p + 2)*Mp
(12:45)>%%(Mp)
%4 = 0
(12:45)>

a different simplification ?

and now the simplification I got the last time is lining up to the same, almost like I didn't have simplify on.

ATH · 2011-05-20, 16:19

Quote:

Originally Posted by R.D. Silverman

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?

x-1 is divisible by M_p-1:

x-1 = M_p²*(p-1) - M_p*(p-2) - 1 = M_p²*p - M_p² - M_p*p + 2*M_p - 1 = (M_p-1) * (M_p*p-M_p+1)

I don't know why I couldn't see this before, of course it's Fermat's PRP test :(

R.D. Silverman · 2011-05-20, 16:40

Quote:

Originally Posted by ATH

x-1 is divisible by M_p-1:

x-1 = M_p²*(p-1) - M_p*(p-2) - 1 = M_p²*p - M_p² - M_p*p + 2*M_p - 1 = (M_p-1) * (M_p*p-M_p+1)

I don't know why I couldn't see this before, of course it's Fermat's PRP test :(

But it's a BAD way to do it. The exponent is twice as long as necessary!

ATH · 2011-05-20, 17:45

See the OP. This was meant to be a new primality test for mersenne numbers, not a PRP test, written in an obscure way. I cleaned up the expressions some but missed the last step that showed it was just a Fermat PRP test.

Probably because I was hoping this was a new and interesting primality test and disregarding the logic of how improbable it all was, also because numerically it seemed to work.

science_man_88 · 2011-05-20, 17:55

Quote:

Originally Posted by ATH

See the OP. This was meant to be a new primality test for mersenne numbers, not a PRP test, written in an obscure way. I cleaned up the expressions some but missed the last step that showed it was just a Fermat PRP test.

Probably because I was hoping this was a new and interesting primality test and disregarding the logic of how improbable it all was, also because numerically it seemed to work.

is there even an equivalent in the LL test to some of this ( I know of the a and b =0 mod k kinda is like the reason to use the LL test) maybe we can put the LL test in a form like the op tried to put the fermat test and work back to a easier test ?

R.D. Silverman · 2011-05-20, 19:35

Quote:

Originally Posted by science_man_88

is there even an equivalent in the LL test to some of this ( I know of the a and b =0 mod k kinda is like the reason to use the LL test) maybe we can put the LL test in a form like the op tried to put the fermat test and work back to a easier test ?

Huh????? Easier than LL?? Easier in what way?
Modular exponentiation is certainly not any easier than LL.

Any purported new tests must perform fewer than p multiplications to
test M_p, otherwise it is just re-inventing a square wheel.

science_man_88 · 2011-05-20, 19:48

Quote:

Originally Posted by R.D. Silverman

Huh????? Easier than LL?? Easier in what way?
Modular exponentiation is certainly not any easier than LL.

Any purported new tests must perform fewer than p multiplications to
test M_p, otherwise it is just re-inventing a square wheel.

so (p-2) squaring + (p-2) subtraction + (p-2) remainder = p multiplication ?

CRGreathouse · 2011-05-20, 22:41

The squarings and modulus you speak of are parts of a single modular squaring (which may not have distinct "squaring" and "reducing" steps). The subtractions are cheap compared to the squarings. Technically, squaring is different from (easier than) multiplication, but at a minimum a test designed to supplant LL can't do more than p full-length multiplications, because those alone would take longer than the LL.

2011-05-20, 14:28	#24
science_man_88 "Forget I exist" Jul 2009 Dartmouth NS 2·3·23·61 Posts	Code: (11:16)>(-Mp^2 + 2Mp)%(Mp^2-Mp) %232 = Mp this proves my early PARI incorrect it seems ( being 0 mod Mp and 0 mod Mp-1 leads to, 0 mod (Mp^2-Mp)) the first term according to previous PARI was (Mp^2-Mp)p easily 0 mod (Mp^2-Mp). the second appears to show Mp mod that number making the whole equation Mp mod that number but if I subtract 1 ( to give x-1) I get Mp-1 which lines up with you. I may have to virus check my computer now. or figure out a way to get PARI to stop giving bad results it seems.

2011-05-20, 17:45	#29
ATH Einyen Dec 2003 Denmark 2·17·101 Posts	See the OP. This was meant to be a new primality test for mersenne numbers, not a PRP test, written in an obscure way. I cleaned up the expressions some but missed the last step that showed it was just a Fermat PRP test. Probably because I was hoping this was a new and interesting primality test and disregarding the logic of how improbable it all was, also because numerically it seemed to work. Last fiddled with by ATH on 2011-05-20 at 17:49

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, 22:41	#33
CRGreathouse Aug 2006 5,987 Posts	The squarings and modulus you speak of are parts of a single modular squaring (which may not have distinct "squaring" and "reducing" steps). The subtractions are cheap compared to the squarings. Technically, squaring is different from (easier than) multiplication, but at a minimum a test designed to supplant LL can't do more than p full-length multiplications, because those alone would take longer than the LL.