dsalgo/
jacobi_symbol.rs

1/// compute jacobi symbol (a/modulus)
2/// https://en.wikipedia.org/wiki/Jacobi_symbol
3
4pub fn jacobi_symbol(
5    modulus: u64,
6    mut a: u64,
7) -> i8 {
8    let mut n = modulus;
9
10    assert!(a < n && n & 1 == 1);
11
12    let mut symbol = 1;
13
14    while a != 0 {
15        let ctz = a.trailing_zeros();
16
17        if ctz & 1 == 1 && (n & 7 == 3 || n & 7 == 5) {
18            symbol = -symbol;
19        }
20
21        a >>= ctz;
22
23        if a & 3 == 3 && n & 3 == 3 {
24            symbol = -symbol;
25        }
26
27        n %= a;
28
29        std::mem::swap(&mut a, &mut n);
30    }
31
32    if n != 1 {
33        0
34    } else {
35        symbol
36    }
37}
38
39#[cfg(test)]
40
41mod tests {
42
43    #[test]
44
45    fn test() {}
46}