mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2014-10-12, 09:10   #1
primus
 
Jul 2014
Montenegro

2·13 Posts
Default Conjectured Primality Test for Specific Class of Mersenne Numbers

Conjecture

Let M_p=2^p-1 such that p is prime and p\equiv 5 \pmod{6}

Let S_i=S_{i-1}^8-8\cdot S_{i-1}^6+20\cdot S_{i-1}^4-16 \cdot S_{i-1}^2+2 with S_0=4 , then

M_p is prime iff S_{(p-2)/3} \equiv 0 \pmod{M_p}

Maxima Implementations

LL Test

Code:
p:9689;
(s:4,M:2^p-1,
for i from 1 thru (p-2) do (s:mod(s^2-2,M)))$
(if(s=0) then print("prime") else print("composite"));
Conjecture

Code:
p:9689;
(s:4,M:2^p-1,
for i from 1 thru (p-2)/3 do (s:mod(s^8-8*s^6+20*s^4-16*s^2+2,M)))$
(if(s=0) then print("prime") else print("composite"));
Maxima implementation of this modified test is approximately two times faster than Maxima implementation of original Lucas-Lehmer test .

Maybe someone on this forum can prove or disprove this conjecture .
primus is offline   Reply With Quote
Old 2014-10-12, 09:25   #2
axn
 
axn's Avatar
 
Jun 2003

23×3×193 Posts
Default

Quote:
Originally Posted by primus View Post
Maybe someone on this forum can prove or disprove this conjecture .
This isn't a new test. This is just the LL-test, disguised by using a polynomial which combines 3 iterations of LL into 1. It is only faster because of the interpreted nature of your implementation. I'm betting that the plain version will be faster for larger p (because 3 iterations of s^2-2 should be faster than the deg-8 poly).

EDIT:-
Code:
LL1(p)={my(s=Mod(4,2^p-1)); for(i=1,p-2, s=s^2-2); s==0}
LL2(p)={my(s=Mod(4,2^p-1)); for(i=1,(p-2)/3, s=s^8-8*s^6+20*s^4-16*s^2+2); s==0}
LL3(p)={my(s=Mod(4,2^p-1)); for(i=1,(p-2)/3, s=((s^2-2)^2-2)^2-2); s==0}
LL1(9689)
time = 1,280 ms.
LL2(9689)
time = 3,511 ms.
LL3(9689)
time = 1,276 ms.
In PARI/GP, your version is nearly 3 times slower.

Last fiddled with by axn on 2014-10-12 at 09:31
axn is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Lucasian Pseudoprimality Hypothesis for Specific Class of k 2^n-1 primus Miscellaneous Math 14 2015-07-04 15:42
Pseudoprimality Hypothesis for Specific Class of Generalized Fermat Numbers primus Miscellaneous Math 1 2015-03-25 22:18
Disproven Primality Test for Specific Class of kb^n-1 primus Computer Science & Computational Number Theory 8 2014-08-21 15:16
Conjectured Primality Test for Specific Class of k6^n-1 primus Computer Science & Computational Number Theory 16 2014-08-15 01:15
Conjectured Primality Test for 2^p-1, (2^p+1)/3 and (2^2^n+1) T.Rex Math 75 2007-09-04 07:53

All times are UTC. The time now is 02:32.

Wed Jul 8 02:32:22 UTC 2020 up 105 days, 5 mins, 0 users, load averages: 3.17, 2.67, 2.41

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.