20190424, 10:41  #1 
Sep 2002
Database er0rr
13·251 Posts 
GMP to use BPSW
https://gmplib.org/listarchives/gmp...il/006311.html
I guess we will have to wait and see what variation of BPSW GMP uses. 
20190424, 13:07  #2  
"Dana Jacobsen"
Feb 2011
Bangkok, TH
2·11·41 Posts 
Quote:


20190424, 16:07  #3 
Jan 2008
France
17×31 Posts 
It looks like there already is a BPSW implementation in minigmp:
https://gmplib.org/repo/gmp/file/tip...gmp/minigmp.c 
20190515, 01:34  #4  
Sep 2002
Database er0rr
CBF_{16} Posts 
Quote:
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^2x+1) else (x+1)^(n+1) == 2+2^a (mod n, x^22^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 Last fiddled with by paulunderwood on 20190515 at 01:57 

20190517, 20:19  #5  
Sep 2002
Database er0rr
13·251 Posts 
Quote:
Last fiddled with by paulunderwood on 20190517 at 20:32 

20190616, 21:29  #6 
Sep 2002
Database er0rr
3263_{10} Posts 
powers of 2 variant of BPSW
Here is another variant of BPSW. The Lucas sequence is over x^22^r*x+1, r minimal.
Code:
{tst(n)=local(a,LEN,BIN,k,va,vb); if(n==2n==3,return(1)); if(gcd(6,n)==1&&!issquare(n)&&Mod(2,n)^n==2, a=4;while(kronecker(a^24,n)!=1,a=a<<1;if(gcd(a^3a,n)!=1,return(0))); BIN=binary(n);LEN=#BIN1;va=Mod(2,n);vb=Mod(a,n); for(k=1,LEN, if(BIN[k]==1,va=va*vba;vb=vb^22,vb=va*vba;va=va^22)); k=kronecker(a+2,n);if(va==a*k&&vb==2*k,return(1),return(0)),return(0))} Last fiddled with by paulunderwood on 20190616 at 23:14 
20200125, 17:37  #7  
Sep 2002
Database er0rr
13·251 Posts 
GMP 6.2.0 released
Quote:
Quote:
Last fiddled with by paulunderwood on 20200125 at 17:52 

20200125, 19:23  #8 
"Seth"
Apr 2019
155_{10} Posts 
I wrote that documentation! Excited to finally see it go live

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
BPSW Primality Test  ATH  Computer Science & Computational Number Theory  33  20140813 22:25 