A collection of efficient number theoretic algorithms and data structures
Fermat contains algorithms and data structures to efficiently
compute many important results in number theory. Most methods are
based off of MATH 365 at Rice University and A Friendly
Introduction to Number Theory by Joseph H. Silverman.
- Arithmetic functions and the dirichlet convolution
- Continued fractions
- Cryptographic operations and the RSA algorithm
- Efficient algorithms to solve common diophantine equations
- Linear, Sum of Squares, Pell-like, etc.
- Common factorization strategies
- Primality testing (Rabin-Miller)
- Operations with quadratic reciprocity and the Jacobi symbol
- Random (large) prime generation
- An algorithm to compute modular inverses
- Various utility methods
- And more to come ...
Set up the environment and install dependencies.
# start in the repository directory
python3 -m venv venv
. venv/bin/activate
pip install -r requirements.txt
All code is available in the /fermat directory.
This project also contains a REST API that generates arbitrarily large public/private keys for RSA encryption. You can run the server with
python3 run_server.py
The server will then be available at localhost:2345. The only
available GET endpoint is /get-keys/<min_bits>, where min_bits
is an integer that specifies the minimum allowable bits in the
public key. The private key and modulus will have about twice
as many bits.
{
min_bits: 10,
publicKey: "0x3d981",
privateKey: "0x568bcc181",
modulus: "0xdab06fce1"
}
Tests are set up with the unittest module. You can run them with
python3 -m unittest