Number theory library written in python
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Failed to load latest commit information.

Python Number theory library


  • 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