View Single Post
Old 2014-10-12, 09:25   #2
axn
 
axn's Avatar
 
Jun 2003

496210 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