Programs and libraries in C for testing prp

[enzocreti]

Are there C programs or libraries allowing probable primes tests for very large numbers (100k+ digits)?
Thanks

[paulunderwood]

Originally Posted by enzocreti

Are there C programs or libraries allowing probable primes tests for very large numbers (100k+ digits)?
Thanks

At "100k+ digits" there is GWNUM, but why bother when you can use OpenPFGW?

[danaj]

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.

[enzocreti]

Originally Posted by danaj

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.

thanks

and a compiler for C? What do you suggest?

[enzocreti]

What about ispseudoprime(a,b) function in Perl? Is it fast?

[M344587487]

Originally Posted by enzocreti

thanks

and a compiler for C? What do you suggest?

Maybe I'm misunderstanding the question, but gcc of course.

[rogue]

Originally Posted by enzocreti

thanks

and a compiler for C? What do you suggest?

There is a build of pfgw already available on sourceforge. You don't need to compile it.

[danaj]

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

  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  ecpp-dj 1.04

An aside here that Pari/GP's ECPP now easily beats my ECPP implementation. At 1000 digits, PFGW doesn't run as fast as the programs using GMP.

3443 digits 305136484659*2^11399-1

  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]

32523 digits 1124044292325*2^107999-1

    3.6  PFGW 3.8.3 3-PRP
   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)

79911 digits 183027*2^265440-1

   19.1  PFGW 3.8.3 3-PRP
  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)

[paulunderwood]

Originally Posted by danaj

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

  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  ecpp-dj 1.04

An aside here that Pari/GP's ECPP now easily beats my ECPP implementation. At 1000 digits, PFGW doesn't run as fast as the programs using GMP.

@Dana. I ran 1000 rounds of GMP vs. GWNUM on a 4770k at 1000 digits and obtained a completely different timing ratio to yours above. Maybe your ratio is explained by the fire-up time of PFGW!

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?

[danaj]

Originally Posted by paulunderwood

@Dana. I ran 1000 rounds of GMP vs. GWNUM on a 4770k at 1000 digits and obtained a completely different timing ratio to yours above. Maybe your ratio is explained by the fire-up time of PFGW!

It is quite possible.

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.