mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2019-04-24, 10:41   #1
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

13·251 Posts
Default 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.
paulunderwood is online now   Reply With Quote
Old 2019-04-24, 13:07   #2
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2·11·41 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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).
danaj is offline   Reply With Quote
Old 2019-04-24, 16:07   #3
ldesnogu
 
ldesnogu's Avatar
 
Jan 2008
France

17×31 Posts
Default

It looks like there already is a BPSW implementation in mini-gmp:


https://gmplib.org/repo/gmp/file/tip...gmp/mini-gmp.c
ldesnogu is offline   Reply With Quote
Old 2019-05-15, 01:34   #4
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

CBF16 Posts
Default

Quote:
Originally Posted by ldesnogu View Post
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
File Type: c hybrid.c (3.9 KB, 96 views)

Last fiddled with by paulunderwood on 2019-05-15 at 01:57
paulunderwood is online now   Reply With Quote
Old 2019-05-17, 20:19   #5
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

13·251 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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
File Type: c hybrid.c (4.4 KB, 99 views)

Last fiddled with by paulunderwood on 2019-05-17 at 20:32
paulunderwood is online now   Reply With Quote
Old 2019-06-16, 21:29   #6
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

326310 Posts
Default 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
paulunderwood is online now   Reply With Quote
Old 2020-01-25, 17:37   #7
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

13·251 Posts
Default 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
paulunderwood is online now   Reply With Quote
Old 2020-01-25, 19:23   #8
SethTro
 
SethTro's Avatar
 
"Seth"
Apr 2019

15510 Posts
Default

I wrote that documentation! Excited to finally see it go live
SethTro is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 20:28.

Fri Jul 3 20:28:51 UTC 2020 up 100 days, 18:01, 2 users, load averages: 1.66, 1.52, 1.52

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.