machine_prime/
lib.rs

1// lang_items triggers a warning as of 1.74
2
3//! Machine-prime provides fast implementations of the current best primality tests for 64-bit and optionally 128-bit integers.
4//!
5//! Machine-prime has 5 different variants. Tiny,Lucas, SSMR, Wide and QFT. Implementation specifics is given below for each. 
6//! First the algorithm is described then a general estimate of time complexity is provided. is_prime_wc never uses trial
7//! division. Time complexity is expressed as a ratio of 1 fermat test base-15 and taken as an average of the input candidates. 
8//! is_prime's time complexity is approximated from the computation time for the interval [2^64-10^8;2^64]. 
9//! is_prime_wc's time complexity is calculated from evaluating 2^64-59.  
10//!
11//! Additionally there are the Wide and QFT features which extend the functions to 2^128. They are much slower than the previous
12//! algorithms due to extended precision arithmetic. They have also not been proven to have no errors below 2^128.
13//! 
14//! Enabling the Internal feature, exposes the internal arithmetic for integration and reducing code duplication in 
15//! other number theory software.  
16//! # Default/SSMR
17//! Algorithm 
18//! - Trial Division by first 129 primes
19//! - Base-2 strong fermat test
20//! - Look-up table of 262144 candidate bases for a strong fermat test
21//! - Branches for n < 2^47 to use a single strong fermat test
22//!
23//! Properties
24//! - is_prime complexity: n < 2^47 0.154; n > 2^47 0.167
25//! - is_prime_wc complexity: n < 2^47 1; n > 2^47 2.0
26//! - Data Memory: 525472 bytes
27//! # Lucas
28//! Algorithm 
29//! - Trial Division by first 129 primes
30//! - Base-2 strong fermat test
31//! - Lucas sequence test using a look-up table of parameters
32//!
33//! Properties
34//! - is_prime complexity:  0.2
35//! - is_prime_wc complexity: 2.5
36//! - Data Memory: 1056 bytes
37//! # Tiny/No feature
38//! Algorithm 
39//! - Divison by 2
40//! - Base-2 strong fermat test
41//! - Lucas sequence test using parameters calculated over 2Z+1
42//!
43//! Properties
44//! - is_prime complexity: 0.6
45//! - is_prime_wc complexity: 2.5
46//! - Data Memory: Negligible - no-std Binary compiles to 9.6 kb
47//!
48//! # Wide
49//! Algorithm
50//! - Division by first 129 primes (if Lucas or SSMR feature is enabled)
51//! - Base-2 strong test
52//! - Lucas sequence test
53//! 
54//! Properties
55//! - is_prime_128 complexity: 3.4*t
56//! - is_prime_wc_128 complexity: 3.4*t
57//!
58//! Complexity here is measured against 64-bit. Currently 128-bit runs in approximately 3.4t where t is 64-bit run-time
59//! using the "SSMR" algorithm. 
60//! Branches to whatever algorithm is selected by other features for n < 2^64. 
61//! 
62//! This current implementation uses a modified BPSW test which has no known counterexamples. If one wants to strength it, 
63//! one can use the strong_fermat test exposed by the "internal" feature, to add more tests at some extra cost. Conversely using
64//! QFT can be more efficient.
65//!
66//! # QFT
67//! Algorithm
68//! - Division by first 139 primes (if Lucas or SSMR feature is enabled)
69//! - Base-2 strong test
70//! - Khashin's Quadratic Frobenius test
71//! 
72//! Properties
73//! - is_prime_128 complexity: 4.4*t or 1.3 times the Wide algorithm
74//! - is_prime_wc_128 complexity: 9.8*t or 2.8 times the Wide algorithm
75//!
76//! This algorithm is substantially stronger than the BPSW, and exists as a fallback algorithm incase a BPSW is discovered or the user 
77//! wants greater confidence in accuracy. It however has not been proven to be correct for all inputs and errors may exist.
78
79
80#![no_std]
81//#![allow(internal_features)]
82//#![feature(lang_items)]
83
84
85pub(crate) mod check;
86pub(crate) mod hashbase;
87pub(crate) mod primes;
88
89#[cfg(any(feature="wide",feature="qft"))]
90pub(crate) mod wide;
91#[cfg(feature="qft")]
92pub(crate) mod qft;
93
94pub use check::{is_prime,is_prime_wc};
95#[cfg(any(feature="wide",feature="qft"))]
96pub use wide::{is_prime_128,is_prime_wc_128};
97
98#[cfg(feature="internal")]
99pub use check::*;
100#[cfg(all(feature="internal",feature="wide"))]
101pub use wide::*;
102#[cfg(all(feature="internal",any(feature="lucas",feature="ssmr")))]
103pub use primes::*;
104#[cfg(all(feature="internal",feature="ssmr"))]
105pub use hashbase::FERMAT_WITNESS;
106
107 // Comment out for crates publication
108/*
109#[panic_handler]
110fn panic(_info: &core::panic::PanicInfo) -> ! {
111    loop {}
112}
113
114
115#[lang = "eh_personality"]
116extern "C" fn eh_personality() {}
117
118   End comment out*/
machine_prime/lib.rs

machine_prime/
lib.rs
