This crate provides a beautifully simplistic API for generating large, cryptographically-random, 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.
Add this to your Cargo.toml:
toml
[dependencies]
num-primes = "0.2.0"
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.
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. |
This function will generate a composite number of n-bits.
```rust use num_primes::Generator;
fn main(){ // Generate Composite of 1024 bits let composite = Generator::new_composite(1024); } ```
This function will generate a prime number of n-bits.
```rust use num_primes::Generator;
fn main(){ // Generate two primes (p,q) of 512 bits each let p = Generator::newprime(512); let q = Generator::newprime(512);
// Multiply to get the modulus (n) let n = p * q; } ```
This function will generate a safe prime number of n-bits. This function uses the same tests openssl uses to generate safe primes, which is (n-1)/2.
This function is quite time consuming and should be avoided for large sizes.
```rust use num_primes::Generator;
fn main(){ // Generate Safe Prime of 64 bits | Uses (n-1)/2 to check let safeprime = Generator::safeprime(64); } ```
This function will generate a large unsigned integer of n-bits. This function is faster than generating a composite or prime number due to no checks being done.
```rust use num_primes::Generator;
fn main(){ // Generate a Large Unsigned Integer of 1024 bits without running any checks let x = Generator::new_uint(1024); } ```
WARNING: There is currently a bug that makes verification of certain prime numbers fail. Be careful when using this feature.
This function will verify whether a BigUint type is a composite by returning a boolean value.
```rust 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 iscomposite: bool = Verification::iscomposite(&x);
// Asserts that 'iscomposite' is true asserteq!(is_composite, true); } ```
This function will verify whether a BigUint type is a prime by returning a boolean value.
```rust 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 isprime: bool = Verification::isprime(&x);
// Asserts that 'isprime' is true asserteq!(is_prime, true); } ```
This function will verify whether a BigUint type is a safe prime by returning a boolean value.
```rust 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 issafeprime: bool = Verification::issafeprime(&x);
// Asserts that is_safe_prime is true
asserteq!(issafe_prime, true);
}
```
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:
&BigUint | primef64 | constantu32 | constantIt follows the following equation:
- Return
m's Greatest Prime Factor asp
- if
p<=log(n)cthen its p-smooth- if
p>log(n)cthen its not p-smooth
```rust use num::traits::FromPrimitive; use numbigint::BigUint; use numprimes::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 7-smooth
assert_eq!(result, true);
} ```
NOTICE: Factorization is still in the works.
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.
```rust 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"),
}
} ```
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.
n is even, divide by 2n must be odd.
n_sqrt = Take the square root of ni = 3 to n_sqrt
i / n
n by ii dividing by n,
i by 2 and continuen is a prime number and n > 2
nThe Prime Number Generation and parts of its code is based on Snips-AI'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:
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
The numbers go through multiple tests to determine whether they are composite or prime.
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 are generated simply by checking if (p-1)/2 is a prime with the tests listed above.
https://security.stackexchange.com/questions/176394/how-does-openssl-generate-a-big-prime-number-so-fast
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.
Num-Primes may be useful in certain situations, like in embedded systems or where OpenSSLis overkill.
OpenSSL-prime:
(n-1)/2 but is much more efficientNum-Primes:
(n-1)/2 but takes much longer for unknown reasonsnum-primes and ramp-primesramp-primes is the original implementation of the prime number generator using the ramp library.
num-primes is the improved implementation using the num library and is available on stable release with no_std support.
Uses num, a pure-rust 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-primes has:
Uses ramp, a high-performance multiple-precision (aka "BigNum") library for working with numbers bigger than can normally be handled.
ramp-primes is:
Licensed under either of
Apache License, Version 2.0
MIT license
at your option.
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.