prime_formula/prime/
mod.rs

1//! Library for generating likely primes in the range 10^9 to 10^38
2//!
3//! The algorithm uses The Periodic Table of Primes to select candidates
4//! for prime numbers within the given range, and then in parallel runs
5//! a u128 optimized version of the Miller-Rabin tests to find likely primes
6//!
7//! For primes below 10^18 then a deterministic algorithm will be used
8//! which greatly increases the likelihood of finding true primes. Above
9//! this limit, the probabilistic variant of the algorithm will be used
10//! which may return pseudoprimes unless the number of iterations (k) is
11//! set sufficiently high.
12//
13// Copyright: Adam Cottrell (cottrela@gmail.com)
14
15use rayon::prelude::*;
16
17use crate::common::{PRIME_ROOTS, align_to_cycle};
18pub mod primality;
19
20/// Generate huge prime numbers using a primality test
21///
22/// Using primality tests is quicker for very large prime
23/// numbers, but considerably longer than a sieve for smaller
24/// prime numbers.
25
26#[derive(Debug, PartialEq)]
27pub enum PrimalityTest {
28    MillerRabinDeterministic,
29    MillerRabinProbabilistic,
30}
31
32/// Use the formula of primes to find large primes
33pub struct PrimeFormula {
34    k: u32,              // Number of tests to use (limited to 48 in deterministic mode)
35    mode: PrimalityTest, // Primality test
36}
37
38impl PrimeFormula {
39    pub fn new(mode: PrimalityTest, k: u32) -> Self {
40        PrimeFormula { k, mode }
41    }
42
43    /// Get primes within the start/end range (inclusive)
44    ///
45    /// Note that primes below 11 will not be found using this
46    /// formula, and so must be manually added by the caller if
47    /// needed.
48    ///
49    /// This function returns the primes in order of their roots,
50    /// therefore may need sorting before use. Set get_primes.
51    pub fn get_unsorted_primes(&self, start: u128, end: u128) -> Vec<u128> {
52        let (b_start, b_end) = align_to_cycle(start, end);
53        let primes: Vec<u128> = PRIME_ROOTS
54            .into_par_iter()
55            .flat_map(|root| {
56                (b_start..b_end)
57                    .map(|i| root as u128 + i * 210)
58                    .filter(|p| *p >= start && *p <= end) // Filter by range
59                    .filter(|p| {
60                        primality::is_prime(
61                            p,
62                            self.k,
63                            self.mode == PrimalityTest::MillerRabinDeterministic,
64                        )
65                    })
66                    .collect::<Vec<u128>>() // Collect inner results
67            })
68            .collect(); // Collect parallel results
69
70        primes
71    }
72
73    /// Get primes within the start/end range (inclusive)
74    ///
75    /// Note that primes below 11 will not be found using this
76    /// formula, and so must be manually added by the caller if
77    /// needed.
78    ///
79    /// This function returns the primes sorted. To get the unsorted
80    /// primes, which is faster, use get_unsorted_primes.
81    pub fn get_primes(&self, start: u128, end: u128) -> Vec<u128> {
82        let mut primes = self.get_unsorted_primes(start, end);
83
84        primes.par_sort_unstable();
85        primes
86    }
87}
88
89#[cfg(test)]
90mod tests {
91    use super::*;
92
93    #[test]
94    fn test_deterministic_primes() {
95        let primes;
96        let inst = PrimeFormula::new(PrimalityTest::MillerRabinDeterministic, 2);
97
98        // Check the first million primes
99        primes = inst.get_primes(11, 1_000_000);
100        assert_eq!(primes.len(), 78498 - 4); // Number of primes below 1e6, excluding 2,3,5,7
101        assert_eq!(primes[0], 11); // First prime from root 11
102        assert_eq!(primes[78498 - 4 - 1], 999_983); // Last prime before 1e6
103    }
104
105    #[test]
106    fn test_probabilistic_primes() {
107        // Very low chance of failure for low order primes
108        let primes;
109        let inst = PrimeFormula::new(PrimalityTest::MillerRabinProbabilistic, 4);
110
111        // Check the first million primes
112        primes = inst.get_primes(11, 1_000);
113        assert_eq!(primes.len(), 168 - 4); // Number of primes below 1e6, excluding 2,3,5,7
114        assert_eq!(primes[0], 11); // First prime from root 11
115        assert_eq!(primes[168 - 4 - 1], 997); // Last prime before 1e6
116    }
117}
prime_formula/prime/mod.rs

prime_formula/prime/
mod.rs
