mersenneforum.org > Math New test for Mersenne prime
 Register FAQ Search Today's Posts Mark Forums Read

2011-05-20, 14:11   #23
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

100000111000102 Posts

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

 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 + 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.
2011-05-20, 15:47   #25
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

100000111000102 Posts

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 ?

2011-05-20, 16:11   #26
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

100000111000102 Posts

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.

2011-05-20, 16:19   #27
ATH
Einyen

Dec 2003
Denmark

65528 Posts

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 Mp-1:

x-1 = Mp2*(p-1) - Mp*(p-2) - 1 = Mp2*p - Mp2 - Mp*p + 2*Mp - 1 = (Mp-1) * (Mp*p-Mp+1)

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

Last fiddled with by ATH on 2011-05-20 at 16:20

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

"Bob Silverman"
Nov 2003
North of Boston

11101010100102 Posts

Quote:
 Originally Posted by ATH x-1 is divisible by Mp-1: x-1 = Mp2*(p-1) - Mp*(p-2) - 1 = Mp2*p - Mp2 - Mp*p + 2*Mp - 1 = (Mp-1) * (Mp*p-Mp+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!

 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
2011-05-20, 17:55   #30
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2·3·23·61 Posts

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 ?

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

"Bob Silverman"
Nov 2003
North of Boston

750610 Posts

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.

2011-05-20, 19:48   #32
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

20E216 Posts

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 ?

 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post dabaichi News 571 2020-10-26 11:02 paulunderwood Miscellaneous Math 18 2017-01-26 20:33 spkarra Math 21 2015-01-23 18:13 jocelynl Math 8 2006-10-20 19:36 illman-q Miscellaneous Math 33 2004-09-19 05:02

All times are UTC. The time now is 22:19.

Sat Jan 28 22:19:09 UTC 2023 up 163 days, 19:47, 0 users, load averages: 0.98, 1.21, 1.26