 mersenneforum.org > Math New test for Mersenne prime
 Register FAQ Search Today's Posts Mark Forums Read  2011-05-19, 21:09   #12
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

841810 Posts Quote:
 Originally Posted by ATH 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.   2011-05-19, 22:14   #13
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts Quote:
 Originally Posted by ATH 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.
if I did the math correct.   2011-05-19, 22:20   #14
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts Quote:
 Originally Posted by science_man_88 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   2011-05-20, 01:40   #15
CRGreathouse

Aug 2006

598710 Posts Quote:
 Originally Posted by ATH 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 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   2011-05-20, 11:31 #16 ATH Einyen   Dec 2003 Denmark 2·17·101 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: 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?   2011-05-20, 11:49   #17
TimSorbet
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

11×389 Posts 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 new-mers-test.zip (46.4 KB, 125 views)

Last fiddled with by TimSorbet on 2011-05-20 at 12:00   2011-05-20, 12:27   #18
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

1D5416 Posts 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: 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.   2011-05-20, 12:48   #19
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2·3·23·61 Posts 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 ( so x-1 shouldn't also be).   2011-05-20, 13:13   #20
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22·1,877 Posts Quote:
 Originally Posted by science_man_88 2) no in fact I find using PARI that x is 0 mod ( 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.   2011-05-20, 13:20   #21
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts 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.

Last fiddled with by science_man_88 on 2011-05-20 at 13:23   2011-05-20, 14:05   #22
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22×1,877 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.
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?   Thread Tools Show Printable Version Email this Page 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 09:13.

Thu Feb 2 09:13:53 UTC 2023 up 168 days, 6:42, 1 user, load averages: 0.60, 0.75, 0.80