This is a repo for studying the distribution of prime numbers and to gain an intuition for number theoretical theories. This the author's first encounter with Rust, so comments and contributions are welcome.
| Module | Contents |
|---|---|
src/fermat.rs |
Fermat primality test, based on Fermat's little theorem |
src/miller_rabin.rs |
Miller–Rabin probabilistic primality test |
src/carmichael.rs |
Classifies a composite as plain composite, Fermat liar, or Carmichael number by brute force over all bases |
src/korselt.rs |
Carmichael check via Korselt's criterion: n is Carmichael iff it is composite, square-free, and p − 1 divides n − 1 for every prime factor p |
src/aks.rs |
The binomial-coefficient primality test underlying AKS: n is prime iff n divides C(n, k) for all 0 < k < n |
src/common.rs |
Shared helpers: modular exponentiation, gcd, square and factor utilities |
cargo run # runs a small demo of the tests above
cargo test # runs the unit tests
An Ulam Spiral indicates the distribution of prime numbers along the spiral. Source: Wikimedia.