mersenneforum.org GMP to use BPSW
 Register FAQ Search Today's Posts Mark Forums Read

 2019-04-24, 10:41 #1 paulunderwood     Sep 2002 Database er0rr 62068 Posts GMP to use BPSW https://gmplib.org/list-archives/gmp...il/006311.html I guess we will have to wait and see what variation of BPSW GMP uses.
2019-04-24, 13:07   #2
danaj

"Dana Jacobsen"
Feb 2011
Bangkok, TH

17×53 Posts

Quote:
 Originally Posted by paulunderwood https://gmplib.org/list-archives/gmp...il/006311.html I guess we will have to wait and see what variation of BPSW GMP uses.
It is about time. I know WraithX submitted his code to them years ago. IIRC it is a slower than mine, though in a nice neat library. I'd like to see either a standard Selfridge strong Lucas test, or the full extra strong test (which is also faster).

 2019-04-24, 16:07 #3 ldesnogu     Jan 2008 France 22×131 Posts It looks like there already is a BPSW implementation in mini-gmp: https://gmplib.org/repo/gmp/file/tip...gmp/mini-gmp.c
2019-05-15, 01:34   #4
paulunderwood

Sep 2002
Database er0rr

C8616 Posts

Quote:
 Originally Posted by ldesnogu It looks like there already is a BPSW implementation in mini-gmp: https://gmplib.org/repo/gmp/file/tip...gmp/mini-gmp.c
It would be interesting to see how (for a probable prime) it compares with the attached code, which (does some alignment for modular reduction and) tests the following:

if n%4 == 3 then (x+2)^(n+1) == 5 (mod n, x^2+1) else
if n%6 == 5 then (x+2)^(n+1) == 7 (mod n, x^2-x+1) else
(x+1)^(n+1) == 2+2^a (mod n, x^2-2^a*x+1)

The code uses shifts for some multiplications for the latter. Using FFT will be a game changer.

I use:
Code:
time echo 'print(10^1000+453)' | gp -q | ./hybrid
Attached Files
 hybrid.c (3.9 KB, 85 views)

Last fiddled with by paulunderwood on 2019-05-15 at 01:57

2019-05-17, 20:19   #5
paulunderwood

Sep 2002
Database er0rr

2·7·229 Posts

Quote:
 Originally Posted by paulunderwood It would be interesting to see how (for a probable prime) it compares with the attached code, which (does some alignment for modular reduction and) tests the following: if n%4 == 3 then (x+2)^(n+1) == 5 (mod n, x^2+1) else if n%6 == 5 then (x+2)^(n+1) == 7 (mod n, x^2-x+1) else (x+1)^(n+1) == 2+2^a (mod n, x^2-2^a*x+1) The code uses shifts for some multiplications for the latter. Using FFT will be a game changer. I use: Code: time echo 'print(10^1000+453)' | gp -q | ./hybrid
"Alignment" has been corrected in the attached update, and the loops unrolled.
Attached Files
 hybrid.c (4.4 KB, 90 views)

Last fiddled with by paulunderwood on 2019-05-17 at 20:32

 2019-06-16, 21:29 #6 paulunderwood     Sep 2002 Database er0rr 320610 Posts powers of 2 variant of BPSW Here is another variant of BPSW. The Lucas sequence is over x^2-2^r*x+1, r minimal. Code: {tst(n)=local(a,LEN,BIN,k,va,vb); if(n==2||n==3,return(1)); if(gcd(6,n)==1&&!issquare(n)&&Mod(2,n)^n==2, a=4;while(kronecker(a^2-4,n)!=-1,a=a<<1;if(gcd(a^3-a,n)!=1,return(0))); BIN=binary(n);LEN=#BIN-1;va=Mod(2,n);vb=Mod(a,n); for(k=1,LEN, if(BIN[k]==1,va=va*vb-a;vb=vb^2-2,vb=va*vb-a;va=va^2-2)); k=kronecker(a+2,n);if(va==a*k&&vb==2*k,return(1),return(0)),return(0))} Last fiddled with by paulunderwood on 2019-06-16 at 23:14
2020-01-25, 17:37   #7
paulunderwood

Sep 2002
Database er0rr

2·7·229 Posts
GMP 6.2.0 released

Quote:
 * Functions to detect primality now substitute the first 24 Miller-Rabin iterations with the BPSW test

Quote:
 Function: int mpz_probab_prime_p (const mpz_t n, int reps) Determine whether n is prime. Return 2 if n is definitely prime, return 1 if n is probably prime (without being certain), or return 0 if n is definitely non-prime. This function performs some trial divisions, a Baillie-PSW probable prime test, then reps-24 Miller-Rabin probabilistic primality tests. A higher reps value will reduce the chances of a non-prime being identified as “probably prime”. A composite number will be identified as a prime with an asymptotic probability of less than 4^(-reps). Reasonable values of reps are between 15 and 50. GMP versions up to and including 6.1.2 did not use the Baillie-PSW primality test. In those older versions of GMP, this function performed reps Miller-Rabin tests.

Last fiddled with by paulunderwood on 2020-01-25 at 17:52

 2020-01-25, 19:23 #8 SethTro     "Seth" Apr 2019 2328 Posts I wrote that documentation! Excited to finally see it go live

 Similar Threads Thread Thread Starter Forum Replies Last Post ATH Computer Science & Computational Number Theory 33 2014-08-13 22:25

All times are UTC. The time now is 18:59.

Thu May 28 18:59:00 UTC 2020 up 64 days, 16:32, 0 users, load averages: 1.86, 1.70, 1.56