Wagstaff primes: Difference between revisions

=={{header|PARI/GP}}==

wprp.gp

<syntaxhighlight lang="c">\\ compiler: gp2c option: gp2c-run -g wprp.gp

/* wprp(p): input odd prime p > 5 . */

/* returns 1 if (2^p+1)/3 is a Wagstaff probable prime. */

wprp(p) = {

/* trial division up to a reasonable depth (time ratio tdiv/llr ≈ 0.2) */

my(l=log(p), ld=log(l));

forprimestep(q = 1, sqr(ld)^(l/log(2))\4, p+p,

if(Mod(2,q)^p == -1, return)

);

/* From R. & H. LIFCHITZ July 2000 */

/* see: http://primenumbers.net/Documents/TestNP.pdf */

/* if (2^p+1)/3 is prime ==> 25^2^(p-1) ≡ 25 (mod 2^p+1) */

/* Lucas-Lehmer-Riesel test with fast modular reduction. */

my(s=25, m=2^p-1);

for(i = 2, p,

s = sqr(s);

s = bitand(s,m) - s>>p

);

s==25

}; /* end wprp */

/* get exponents of Wagstaff prps in range [a,b] */

wprprun(a, b) = {

my(t=0, c=0, thr=default(nbthreads));

a = max(a,3);

gettime();

if(a <= 5,

if(a == 3, c++; p = 3; printf("#%d\tW%d\t%2dmin, %2d,%03d ms\n", c, p, t\60000%60, t\1000%60, t%1000));

c++; p = 5; printf("#%d\tW%d\t%2dmin, %2d,%03d ms\n", c, p, t\60000%60, t\1000%60, t%1000);

a = 7

);

parforprime(p= a, b, wprp(p), d, /* wprp(p) -> d copy from parallel world into real world. */

if(d,

t += gettime()\thr;

c++;

printf("#%d\tW%d\t%2dmin, %2d,%03d ms\n", c, p, t\60000%60, t\1000%60, t%1000)

)

)

}; /* end wprprun */

/* if running wprp as script */

\\ export(wprp);

wprprun(2, 42737)</syntaxhighlight>

{{out}}

Done on Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz, 4 hyperthreaded cores.

<pre>#1 W3 0min, 0,000 ms

#2 W5 0min, 0,000 ms

#3 W7 0min, 0,000 ms

#4 W11 0min, 0,000 ms

#5 W13 0min, 0,000 ms

#6 W17 0min, 0,000 ms

#7 W19 0min, 0,000 ms

#8 W23 0min, 0,000 ms

#9 W31 0min, 0,000 ms

#10 W43 0min, 0,000 ms

#11 W61 0min, 0,000 ms

#12 W79 0min, 0,000 ms

#13 W101 0min, 0,000 ms

#14 W127 0min, 0,000 ms

#15 W167 0min, 0,000 ms

#16 W191 0min, 0,000 ms

#17 W199 0min, 0,000 ms

#18 W313 0min, 0,000 ms

#19 W347 0min, 0,000 ms

#20 W701 0min, 0,002 ms

#21 W1709 0min, 0,018 ms

#22 W2617 0min, 0,055 ms

#23 W3539 0min, 0,113 ms

#24 W5807 0min, 0,422 ms

#25 W10501 0min, 2,545 ms

#26 W10691 0min, 2,612 ms

#27 W11279 0min, 3,113 ms

#28 W12391 0min, 4,252 ms

#29 W14479 0min, 7,719 ms

#30 W42737 7min, 33,111 ms

? ##

*** last result: cpu time 1h, 8,965 ms, real time 7min, 33,449 ms.</pre>