Changes for version 0.04

  • Add simple prime_count function. It uses next_prime so is terribly slow for big ranges. However it's a lot faster than the PP code when given a large base and small range e.g. (10**96, 10**96 + 2**18).
  • Add primorial, pn_primorial, and consecutive_integer_lcm functions.
  • Factoring: Add a perfect power test. Add a simple ECM factoring method. Speed up SQUFOF a bit. Complete p-1 rewrite. Much faster and finds more factors. Adjust general factor() mix.
  • Add Pocklington-Lehmer and BLS primality tests. is_prime() uses the BLS test with a quick factoring attempt for numbers less than 2^200, though the chances of success drop off as the size increases. The point is not to cull mismarked probable primes (we use BPSW so this is highly unlikely for these small sizes), but to quickly mark more numbers as definitely prime. Remember to use is_prob_prime if you do not care about this distinction and want the result slightly faster.
  • add is_provable_prime function that calls BLS with much more aggressive factoring.

Modules

Utilities related to prime numbers and factoring, using GMP