dsalgo 0.3.10

A package for Datastructures and Algorithms.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

use crate::{
    montgomery_modular_multiplication_64::MontgomeryMultiplication64,
    power::pow_semigroup,
};

/// n might not be prime.

pub(crate) fn try_euler_criterion(
    n: u64,
    a: u64,
) -> Result<u64, &'static str> {
    assert!(2 < n && n & 1 == 1 && 0 < a && a < n);

    assert!(a % n != 0);

    let multiplier = MontgomeryMultiplication64::new(n);

    let res = pow_semigroup(&|x, y| multiplier.mul(x, y), a, (n - 1) >> 1);

    if res == 1 || res == n - 1 {
        Ok(res)
    } else {
        Err("modulus n cannot be prime.")
    }
}

/// prime modulus p and a != 0 (mod p)
/// user must ensure that p is prime.

pub fn euler_criterion(
    p: u64,
    a: u64,
) -> u64 {
    // TODO: assert p is prime if O(\log{p}) possible
    try_euler_criterion(p, a).unwrap()
}

#[cfg(test)]

mod tests {

    #[test]

    fn test() {
        use super::*;

        assert_eq!(euler_criterion(5, 1), 1); // 1^2, 4^2
        assert_eq!(euler_criterion(5, 2), 4);

        assert_eq!(euler_criterion(5, 3), 4);

        assert_eq!(euler_criterion(5, 4), 1); // 2^2, 3^2
    }
}