6 releases
0.3.0  Dec 6, 2021 

0.2.1  Nov 6, 2021 
0.2.0  Sep 17, 2021 
0.1.2  Jan 11, 2021 
0.1.1  May 9, 2020 
#691 in Math
277 downloads per month
Used in 5 crates
40KB
256 lines
NumPrimes: CSPRNG Large Composite, Prime, Safe Prime Generator
This crate provides a beautifully simplistic API for generating large, cryptographicallyrandom, unsigned integers in rust, including but not limited to composite, prime, and safe prime numbers.
It takes full advantage of the num crate on stable rust.
 Read the About
 Read the License
 Read the Contribution
Notice
Please note there is a critical bug in this program that I cannot seem to fix where it marks some prime numbers as not prime. It is in the millerrabin implementation and I cannot seem to fix it. If anyone is up to it, feel free to look through the issues tab for information about the bug and submit a PR if you find a fix.
Usage
Add this to your Cargo.toml
:
[dependencies]
numprimes = "0.2.0"
Warning
There is currently a major bug in is_prime()
and is_composite()
that makes some values return wrong. For example, a prime can sometimes be marked as composite unless it was generated as they use the same tests to test for primality.
How To Use
There are three main structs that are included in this library
Structs  Description 

Generator  Allows the random generation of composite numbers, prime numbers, and safe prime numbers. 
Verification  Allows the verification of composite, prime, safe prime, and very smooth numbers. 
Factorization  Allows the factorization of Composite and Prime Numbers into their largest Prime Factor. 
Generator
Generate Composite Number
This function will generate a composite number of nbits
.
use num_primes::Generator;
fn main(){
// Generate Composite of 1024 bits
let composite = Generator::new_composite(1024);
}
Generate Prime Number
This function will generate a prime number of nbits
.
use num_primes::Generator;
fn main(){
// Generate two primes (p,q) of 512 bits each
let p = Generator::new_prime(512);
let q = Generator::new_prime(512);
// Multiply to get the modulus (n)
let n = p * q;
}
Generate Safe Prime
This function will generate a safe prime number of nbits
. This function uses the same tests openssl uses to generate safe primes, which is (n1)/2
.
This function is quite time consuming and should be avoided for large sizes.
use num_primes::Generator;
fn main(){
// Generate Safe Prime of 64 bits  Uses (n1)/2 to check
let safe_prime = Generator::safe_prime(64);
}
Generate Large Unsigned Integer
This function will generate a large unsigned integer of nbits
. This function is faster than generating a composite or prime number due to no checks being done.
use num_primes::Generator;
fn main(){
// Generate a Large Unsigned Integer of 1024 bits without running any checks
let x = Generator::new_uint(1024);
}
Verification
WARNING: There is currently a bug that makes verification of certain prime numbers fail. Be careful when using this feature.
Verify Composite Number
This function will verify whether a BigUint
type is a composite by returning a boolean value.
use num_primes::{Generator,Verification};
fn main(){
// Generates Composite Number of 1024 bits
let x = Generator::new_composite(1024);
// Check if the number is a Composite Number
let is_composite: bool = Verification::is_composite(&x);
// Asserts that 'is_composite' is true
assert_eq!(is_composite, true);
}
Verify Prime Number
This function will verify whether a BigUint
type is a prime by returning a boolean value.
use num_primes::{Generator,Verification};
fn main(){
// Generates Prime Number of 1024 bits
let x = Generator::new_prime(1024);
// Check if the number is a Prime Number
let is_prime: bool = Verification::is_prime(&x);
// Asserts that 'is_prime' is true
assert_eq!(is_prime, true);
}
Verify Safe Prime Number
This function will verify whether a BigUint
type is a safe prime by returning a boolean value.
use num_primes::{Generator,Verification};
fn main(){
// Generates a Safe Prime Number of 128 bits
let x = Generator::safe_prime(128);
// Check if the number is a Safe Prime Number
let is_safe_prime: bool = Verification::is_safe_prime(&x);
// Asserts that `is_safe_prime` is true
assert_eq!(is_safe_prime, true);
}
[Experimental] Verify VSN (Smooth Numbers)
EXPERIMENTAL: Please Avoid Using This Function As Of Now
Read Wolfram Alpha  Smooth Numbers
Read Wikipedia  Examples of VSN and VSSR
This function will verify whether a number is a very smooth number. It accepts three parameters as follows:
 m:
&BigUint
 prime  n:
f64
 constant  c:
u32
 constant
It follows the following equation:
 Return
m
's Greatest Prime Factor asp
 if
p
<=
log(n)
^{c} then its psmooth if
p
>
log(n)
^{c} then its not psmooth
use num::traits::FromPrimitive;
use num_bigint::BigUint;
use num_primes::Verification;
fn main() {
// Set BigUint To 7u64
let x: BigUint = BigUint::from_u64(7u64).unwrap();
// Verify Its A Smooth Number with parameters
// m = 7 (&BigUint)
// n = 31.0 (f64)
// c = 5 (u32)
let result: bool = Verification::is_very_smooth_number(&x,31.0,5);
// Print What Type of Smooth Number It Is And Whether Or Not It Is Smooth
println!("Is A {} Smooth Number: {}",x,result);
// This problem should be 7smooth
assert_eq!(result, true);
}
Factorization
NOTICE: Factorization is still in the works.
Prime Factorization
Read GeeksforGeeks  Efficient program to print all prime factors of a given number
This function lets you factorize composite numbers and prime numbers to find their Greatest Prime Factor.
use num_primes::{Generator,Factorization};
fn main() {
// Generates New Unsighed Integer of 32 bits
let uint = Generator::new_uint(32);
// Prime Factorization Returns Option<BigUint>
let factor = Factorization::prime_factor(uint);
// match the Option<BigUint>
match factor {
Some(factor) => println!("Largest Prime Factor: {}",factor),
None => println!("No Prime Factors Found"),
}
}
How Does It Work
The steps are listed below with n
being the input number being factored:
A Primality Check is used first to determine whether the number is a prime or not.
 while
n
is even, divide by 2  After Step 1,
n
must be odd.n_sqrt
= Take the square root ofn
 Start a loop from
i = 3
ton_sqrt
 While
i
/n
 Divide
n
byi
 Divide
 On Failure of
i
dividing byn
, increment
i
by 2 and continue
 increment
 While
 If
n
is a prime number andn
>2
 Return
n
 Return
About
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.

The number is sent to be processed by four tests
Primality Tests
The numbers go through multiple tests to determine whether they are composite or prime.
 A check is done to see if the number is even.
 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 (p1)/2
is a prime with the tests listed above.
OpenSSLPrime vs. NumPrimes
OpenSSL LTS (1.1.1) has a doc page for prime generation, including how safe primes are generated.
OpenSSL should be prefered for serious cryptographic implementations due to the security of their code and their code having been audited.
NumPrimes may be useful in certain situations, like in embedded systems or where OpenSSLis overkill.
OpenSSLprime:
 Generates Safe Primes using
(n1)/2
but is much more efficient  Performs a default of 20 checks on prime numbers.
NumPrimes:
 Generates Safe Primes using
(n1)/2
but takes much longer for unknown reasons  Performs a default of 16 checks on prime numbers through 4 different primality tests
 Supports #[no_std] and stable rust
 May be useful in situations where using OpenSSL would be overkill.
Differences Between numprimes
and rampprimes
rampprimes is the original implementation of the prime number generator using the ramp library.
numprimes is the improved implementation using the num library and is available on stable release with no_std support.
numprimes (Stable)
Uses num, a purerust implementation for numeric types and traits.

num is stable and can work on the Default, Beta, and Nightly Branch

num is in Pure Rust

num implements more features

num has around ~6,000,000 downloads

num is more developed than ramp.
numprimes has:
 Better API and Documentation
 More Functionality
 no_std support
rampprimes (Unstable)
Uses ramp, a highperformance multipleprecision (aka "BigNum") library for working with numbers bigger than can normally be handled.
 ramp only works on unstable rust (the nightly branch).
 ramp is written in Rust and Inline Assembly (security concern)
 ramp is generally faster
 ramp is specifically focused on multipleprecision arithmetic
 ramp has around ~17,000 downloads
 ramp is not as developed as num
rampprimes is:
 The First Implementation
 Generally Faster For Generation
 Less Features
 Only Works On Unstable Rust (Nightly Build)
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
~1.5MB
~26K SLoC