dsalgo/
euler_criterion.rs

1use crate::{
2    montgomery_modular_multiplication_64::MontgomeryMultiplication64,
3    power::pow_semigroup,
4};
5
6/// n might not be prime.
7
8pub(crate) fn try_euler_criterion(
9    n: u64,
10    a: u64,
11) -> Result<u64, &'static str> {
12    assert!(2 < n && n & 1 == 1 && 0 < a && a < n);
13
14    assert!(a % n != 0);
15
16    let multiplier = MontgomeryMultiplication64::new(n);
17
18    let res = pow_semigroup(&|x, y| multiplier.mul(x, y), a, (n - 1) >> 1);
19
20    if res == 1 || res == n - 1 {
21        Ok(res)
22    } else {
23        Err("modulus n cannot be prime.")
24    }
25}
26
27/// prime modulus p and a != 0 (mod p)
28/// user must ensure that p is prime.
29
30pub fn euler_criterion(
31    p: u64,
32    a: u64,
33) -> u64 {
34    // TODO: assert p is prime if O(\log{p}) possible
35    try_euler_criterion(p, a).unwrap()
36}
37
38#[cfg(test)]
39
40mod tests {
41
42    #[test]
43
44    fn test() {
45        use super::*;
46
47        assert_eq!(euler_criterion(5, 1), 1); // 1^2, 4^2
48        assert_eq!(euler_criterion(5, 2), 4);
49
50        assert_eq!(euler_criterion(5, 3), 4);
51
52        assert_eq!(euler_criterion(5, 4), 1); // 2^2, 3^2
53    }
54}
dsalgo/euler_criterion.rs

dsalgo/
euler_criterion.rs
