20190124, 12:31  #1 
Mar 2018
509 Posts 
Programs and libraries in C for testing prp
Are there C programs or libraries allowing probable primes tests for very large numbers (100k+ digits)?
Thanks 
20190124, 16:23  #2 
Sep 2002
Database er0rr
7×467 Posts 

20190124, 20:02  #3 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
902_{10} Posts 
Lots of programs that support big numbers should work. My libraries using GMP work fine. But ..... at 100k+ digits they are quite a bit slower than gwnum. As Paul said, it's easiest to use OpenPFGW to start. If it comes back with a positive result you can use one of the other libraries to churn through another test (e.g. BPSW) if that's something you want.

20190125, 06:56  #4  
Mar 2018
509 Posts 
compiler
Quote:
and a compiler for C? What do you suggest? 

20190125, 08:22  #5 
Mar 2018
509 Posts 
PERL
What about ispseudoprime(a,b) function in Perl? Is it fast?

20190125, 12:04  #6 
"Composite as Heck"
Oct 2017
2×293 Posts 

20190125, 14:14  #7 
"Mark"
Apr 2003
Between here and the
2·11·263 Posts 

20190125, 21:37  #8 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
2×11×41 Posts 
These are timings in seconds from my i6700K running Linux. Your mileage may vary. The speed difference is pretty dramatic, which is why everyone recommends using PFGW to start for big inputs.
1000 digit random prime 517216668078912555...019387837939836679416522197 Code:
0.0337 PRP PFGW 3.8.3 Cquiet k u0 f0 q 0.0073 PRP Perl/ntheory is_pseudoprime($n,3) 0.0073 SPRP Perl/ntheory is_strong_pseudoprime($n,3) 0.0083 SPRP Pari/GP 2.12 ispseudoprime(n,1) 0.0233 BPSW Perl/ntheory is_bpsw_prime($n) 0.0233 BPSW Pari/GP 2.12 ispseudoprime(n) 97.2 ECPP Pari/GP 2.12 isprime(n) \\ ECPP was used for this input 152.6 APR Pari/GP 2.12 isprime(n,2) 203.4 ECPP ecppdj 1.04 3443 digits 305136484659*2^113991 Code:
0.06 PRP PFGW 3.8.3 Cquiet k u0 f0 q 0.18 PRP Perl/ntheory is_pseudoprime($n,3) 0.18 SPRP Perl/ntheory is_strong_pseudoprime($n,3) 0.21 SPRP Pari/GP 2.12 ispseudoprime(n,1) 0.38 BPSW Perl/ntheory is_bpsw_prime($n) 0.40 BPSW Pari/GP 2.12 ispseudoprime(n) 0.23 LLR Perl/ntheory is_prime [recognizes LLR form, uses its LLR proof code] 0.23 LLR Perl/ntheory is_provable_prime [same as above] Code:
3.6 PFGW 3.8.3 3PRP 45.1 Perl/ntheory is_pseudoprime($n,3) 45.0 Perl/ntheory is_strong_pseudoprime($n,3) 46.9 Pari/GP 2.12 ispseudoprime(n,1) 105.8 Perl/ntheory is_bpsw_prime($n) 121.4 Pari/GP 2.12 ispseudoprime(n) Code:
19.1 PFGW 3.8.3 3PRP 363.9 Perl/ntheory is_pseudoprime($n,3) 362.0 Perl/ntheory is_strong_pseudoprime($n,3) 395.5 Pari/GP 2.12 ispseudoprime(n,1) 840.1 Perl/ntheory is_bpsw_prime($n) 961.8 Pari/GP 2.12 ispseudoprime(n) 
20190125, 21:55  #9  
Sep 2002
Database er0rr
7·467 Posts 
Quote:
When I have run incremental n searches with PFGW in the past I am pretty sure GMP is used for numbers less than 300 digits. Or was it 600 digits? Last fiddled with by paulunderwood on 20190125 at 22:00 

20190126, 04:50  #10  
"Dana Jacobsen"
Feb 2011
Bangkok, TH
2·11·41 Posts 
Quote:
Run inside: time for i in `seq 1 100`; do XXX; done for these XXX: 3.252s ./pfgw64s k Cquiet f0 u0 q'...' 2.675s ./prp2 t.txt 1.917s perl le 'use ntheory qw/:all/; print is_strong_pseudoprime("...",3);' Single invocations, again 100 loops: 0.80s ./pfgw64s with input file 0.73s Perl with a loop It looks like gwnum has quite a bit of startup overhead, even compared to firing up Perl. PFGW has even more. But once going PFGW seems to be running nearly the same speed on this machine. I tried base 2 and both strong and normal pseudoprime tests just in case that had some impact. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
GPU Testing programs  nucleon  GPU Computing  5  20110821 04:24 
suggestion: separation of libraries  ixfd64  Software  10  20110120 23:02 
Interested in C/C++ libraries for factoring  PythonPower  Factoring  27  20090528 17:08 
Speed of P1 testing vs. Trial Factoring testing  eepiccolo  Math  6  20060328 20:53 
Large Integer Libraries  andi314  Programming  18  20040621 22:37 