ruby-numtheory

The library is written as C extension and aims to provide fast implementations of common number-theoretical algorithms.

Currently implemented

• powermod (uses sliding window exponentiation)
• miller-rabin test for primality
• standard BPSW primality test
• eratosthenes sieve
• factorization (via trial division)
• factorial (uses PrimeSwing algorithm)
• sigma (σ)
• moebius (μ)
• eulerphi (φ)
• primepi (π)
• fibonacci
• modular inverse
• extended gcd
• primitive pythagorean triple generator
• integer square root
• square root in Z/pZ (for prime p)