machine_prime/
lib.rs

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

machine_prime/
lib.rs
