2 unstable releases
✓ Uses Rust 2018 edition
new 0.2.0  Mar 22, 2020 

0.1.0  Nov 19, 2019 
#88 in Math
23KB
133 lines
rampprimes: A Large, Random Composite and Prime Number Generator
This crate provides a beautifully simplistic API for generating large, cryptographicallyrandom, integers in rust, including but not limited to prime numbers.
It takes full advantage of the RAMP crate, which provides highperformance large integers through inline assembly and a high level, simplistic interface for users to use, as well as lowerlevel components allowing complete control over large integers.
This crate requires the use of the nightly toolchain due to the use of ramp with inlineassembly.
Usage
Add the following to your cargo.toml
:
rampprimes = "0.1.0"
ramp = "0.5"
If you have not already, install the nightly toolchain as this will only work on the nightly branch and then set as default toolchain.
rustup toolchain install nightly
rustup default nightly
Example of Prime Number Generation
use ramp_primes::new_prime;
fn main(){
// Generates two primes (p,q) both of 512 bits
let p = new_prime(512);
let q = new_prime(512);
// Generates the modulus n from p and q
let n = p * q;
}
Example of Safe Prime Number Generation
use ramp_primes::safe_prime;
fn main(){
// Outputs a Large Prime with 64 bits
let p = safe_prime(64);
}
Example of Random Number Generation
use ramp_primes::new_uint;
fn main(){
// Creates a Large Integer of 1024 bits
let x = new_uint(1024);
// Prints out the randomly generated number
println!("x: {}",x);
}
Prime Number Generation Design
The Prime Number Generation and parts of its code is based on SnipsAI's Medium Blog on Generating Prime Numbers.
A conservative attempt is made at deciding whether a number is prime or not. The number goes through the generation phase and 3 tests to determine if its prime:
Generation Phase

A single parameter is passed to the generator function that indicates the number of bits the prime should be.

The userspace CSPRNG is seeded by the operating system to generate the random numbers using the rand crate.

An unsigned integer is generated until it passes the prime test, and before being sent to the test, the LSB is changed to 0 to indicate its odd and its MSB is changed to 1 to make sure its the specified bit length.

The number is sent to be processed by three tests
Primality Tests
The numbers go through multiple tests to determine whether they are composite or prime.

An array of the first 2048 primes is used to check whether the number is divisble by any of the primes in the array.

Fermat's Little Theorem is performed

MillerRabin Primality Test, the gold standard recommended by the official RSA documentation and by NIST on generating primes, is performed with 16 iterations, the same used by Apple's cryptosystem.
If the number passes these tests, it is considered with high probability to be prime. Feel free to verify them yourselves on Wolfram Alpha by simply typing in the prime number.
Safe Primes
Safe Primes are generated simply by checking if 2q + 1 is a prime with the tests listed above.
License
Licensed under either of

Apache License, Version 2.0

MIT license
at your option.
Contribution
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache2.0 license, shall be dual licensed as above, without any additional terms or conditions.
Dependencies
~1MB
~22K SLoC