Number Theory

Elementary Number Theory for Integers in Rust

Functionality

• Primality
• Modular exponentiation
• Legendre symbol

Benchmarks

All benchmarks are performed on i3-4005u, with 4GB memory, your performance will likely exceed the values below.

• Multiplication of 10k words
• Primality check of all numbers in the interval 0;2^32 ,590s
• Probable Primality check of 2^86,243-1, this benchmark is not actually possible as Mersenne primes are hardcoded ,2276.46s

Algorithms

• Multiplication due to Karatsuba
• Euclidean division due to Per Brinch Hansen
• Arbitrary-precision logarithm partly due to J.A Sory and Rust-language developers (fairly trivial)
• Fast primality in the interval 0;2^64 due to Forisek and Jancina with some adjustments by J.A Sory
• Probable prime due to Miller, Rabin and utilizing research by Damgard et al, to optimize for accuracy bounds

Research

• Primes: A Computational Perspective ; Pomerance, Carl Crandall, Richard
• Multiple-Length Division: A Tour of the MineField; Per Brinch Hansen
• Average Case Error Estimates For the Strong Probable Prime Test; Damgard, Landrock, Pomerance