Changes for version 0.36 - 2016-05-21

  • ADDED
    • addmod (a + b) % n
    • mulmod (a * b) % n
    • divmod (a / b) % n
    • powmod (a ^ b) % n
    • invmod (1 / b) % n
    • sqrtmod square root modulo a prime
    • is_primitive_root(a,n) return 1 if 'a' is a primitive root mod n
    • sieve_range(n,width,depth) sieve from n, returning candidate offsets
  • FIXES
    • Allow a leading '+' in inputs.
  • PERFORMANCE
    • znprimroot is much faster with large inputs.
    • Speedup partial sieve with large input.
    • next_prime and prev_prime sieve deeper. ~5% faster with large inputs.
    • AKS using Bernstein (2003) theorem 4.1. 10-20x faster.
    • Speedup for large pn_primorial and primorial. Much faster for very large values, though it will all get swamped by the overhead in returning the large value. This is a great reason to return mpz objects.
  • OTHER
    • Split out factor, primality, and AKS code into separate source files.

Modules

Utilities related to prime numbers and factoring, using GMP