mersenneforum.org  

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

Reply
 
Thread Tools
Old 2011-05-19, 21:09   #12
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts
Default

Quote:
Originally Posted by ATH View Post
I don't use PARI but are you sure it can handle the large numbers? x is larger than (2n-1)2. 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 is offline   Reply With Quote
Old 2011-05-19, 22:14   #13
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
I don't use PARI but are you sure it can handle the large numbers? x is larger than (2n-1)2. I used the GMP library.
{(n-1)}{k^2}+{(n-2)}{k} if I did the math correct.
science_man_88 is offline   Reply With Quote
Old 2011-05-19, 22:20   #14
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

838410 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
{(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.

Last fiddled with by science_man_88 on 2011-05-19 at 22:28
science_man_88 is offline   Reply With Quote
Old 2011-05-20, 01:40   #15
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

Quote:
Originally Posted by ATH View Post
I don't use PARI but are you sure it can handle the large numbers? x is larger than (2n-1)2. 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.

Last fiddled with by CRGreathouse on 2011-05-20 at 01:40
CRGreathouse is offline   Reply With Quote
Old 2011-05-20, 11:31   #16
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

27·52 Posts
Default

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:
Mp=2p-1 is prime if: (Mp-p+2)x-1 == 1 (mod Mp)
where x = Mp2*(p-1) - Mp*(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 Mp2, so it needs around Mp squarings same as the LL test?
ATH is offline   Reply With Quote
Old 2011-05-20, 11:49   #17
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

2·5·7·61 Posts
Default

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!
Attached Files
File Type: zip new-mers-test.zip (46.4 KB, 101 views)

Last fiddled with by Mini-Geek on 2011-05-20 at 12:00
Mini-Geek is offline   Reply With Quote
Old 2011-05-20, 12:27   #18
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

164448 Posts
Default

Quote:
Originally Posted by ATH View Post
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:
Mp=2p-1 is prime if: (Mp-p+2)x-1 == 1 (mod Mp)
where x = Mp2*(p-1) - Mp*(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 Mp2, so it needs around Mp 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.
R.D. Silverman is offline   Reply With Quote
Old 2011-05-20, 12:48   #19
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
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).
science_man_88 is offline   Reply With Quote
Old 2011-05-20, 13:13   #20
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D2416 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2011-05-20, 13:20   #21
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
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.

Last fiddled with by science_man_88 on 2011-05-20 at 13:23
science_man_88 is offline   Reply With Quote
Old 2011-05-20, 14:05   #22
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 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.
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?
R.D. Silverman 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 15:14.


Sun Dec 5 15:14:26 UTC 2021 up 135 days, 9:43, 1 user, load averages: 1.27, 1.29, 1.29

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.