Python Number theory library

Algorithms:

• Greatest common divisor: gdc(a, b)

  • complexity: O(log(min(a,b)))
  • memory: O(log(min(a,b)))
  • description: computes the greatest common divisor between a and b

• Modular Exponentiation: modexp(base, power, mod)

  • complexity: O(log(power))
  • memory: O(log(power))
  • description: computes (base^power) % mod

• Pell's Equation: pell_solutions(n, k)

  • complexity: O(n^(1/2) log n)
  • memory: O(k)
  • desciption: computes a list with the first k solutions of the Pell equation: x^2 - n(y^2) = 1

• Eratosthenes' Sieve: sieve(n)

  • complexity: O(n (log log n))
  • memory: O(n)
  • description: sieve of eratosthenes to find primes less than n

• Miller Rabin Primality Test: miller_rabin(n, k=10)

  • complexity: O(k*(log n)^3)
  • memory:
  • description: find primes less than n with 4^(-k) probability