mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2011-05-20, 14:11   #23
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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 is offline   Reply With Quote
Old 2011-05-20, 14:28   #24
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

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 is offline   Reply With Quote
Old 2011-05-20, 15:47   #25
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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 is offline   Reply With Quote
Old 2011-05-20, 16:11   #26
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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.
science_man_88 is offline   Reply With Quote
Old 2011-05-20, 16:19   #27
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

317610 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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
ATH is online now   Reply With Quote
Old 2011-05-20, 16:40   #28
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by ATH View Post
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!
R.D. Silverman is offline   Reply With Quote
Old 2011-05-20, 17:45   #29
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

317610 Posts
Default

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
ATH is online now   Reply With Quote
Old 2011-05-20, 17:55   #30
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by ATH View Post
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 ?
science_man_88 is offline   Reply With Quote
Old 2011-05-20, 19:35   #31
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2011-05-20, 19:48   #32
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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 ?
science_man_88 is offline   Reply With Quote
Old 2011-05-20, 22:41   #33
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

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.
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 10:49.


Fri Oct 22 10:49:31 UTC 2021 up 91 days, 5:18, 1 user, load averages: 1.02, 1.08, 1.12

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.