fermat

A collection of efficient number theoretic algorithms and data structures

Description

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.

This library includes:

• 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 …

How to use

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.

RSA Encryption API

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.

Example Response

{
    min_bits: 10,
    publicKey: "0x3d981",
    privateKey: "0x568bcc181",
    modulus: "0xdab06fce1"
}

How to test

Tests are set up with the unittest module. You can run them with

python3 -m unittest