mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Miscellaneous Math (https://www.mersenneforum.org/forumdisplay.php?f=56)
-   -   Conjectured Primality Test for Specific Class of Mersenne Numbers (https://www.mersenneforum.org/showthread.php?t=19755)

primus 2014-10-12 09:10

Conjectured Primality Test for Specific Class of Mersenne Numbers
 
[B]Conjecture[/B]

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

Let [TEX]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[/TEX] with [TEX]S_0=4[/TEX] , then

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

[B]Maxima Implementations[/B]

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"));[/CODE]

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"));[/CODE]

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 .

axn 2014-10-12 09:25

[QUOTE=primus;385011]Maybe someone on this forum can prove or disprove this conjecture .[/QUOTE]

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.
[/code]
In PARI/GP, your version is nearly 3 times slower.


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

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