num_bigint_dig/algorithms/
jacobi.rs

1use crate::integer::Integer;
2use num_traits::{One, Signed, Zero};
3
4use crate::BigInt;
5
6/// Jacobi returns the Jacobi symbol (x/y), either +1, -1, or 0.
7/// The y argument must be an odd integer.
8pub fn jacobi(x: &BigInt, y: &BigInt) -> isize {
9    if !y.is_odd() {
10        panic!(
11            "invalid arguments, y must be an odd integer,but got {:?}",
12            y
13        );
14    }
15
16    let mut a = x.clone();
17    let mut b = y.clone();
18    let mut j = 1;
19
20    if b.is_negative() {
21        if a.is_negative() {
22            j = -1;
23        }
24        b = -b;
25    }
26
27    loop {
28        if b.is_one() {
29            return j;
30        }
31        if a.is_zero() {
32            return 0;
33        }
34
35        a = a.mod_floor(&b);
36        if a.is_zero() {
37            return 0;
38        }
39
40        // a > 0
41
42        // handle factors of 2 in a
43        let s = a.trailing_zeros().unwrap();
44        if s & 1 != 0 {
45            let bmod8 = b.get_limb(0) & 7;
46            if bmod8 == 3 || bmod8 == 5 {
47                j = -j;
48            }
49        }
50
51        let c = &a >> s; // a = 2^s*c
52
53        // swap numerator and denominator
54        if b.get_limb(0) & 3 == 3 && c.get_limb(0) & 3 == 3 {
55            j = -j
56        }
57
58        a = b;
59        b = c;
60    }
61}
62
63#[cfg(test)]
64mod tests {
65    use super::*;
66
67    use num_traits::FromPrimitive;
68
69    use crate::BigInt;
70
71    #[test]
72    fn test_jacobi() {
73        let cases = [
74            [0, 1, 1],
75            [0, -1, 1],
76            [1, 1, 1],
77            [1, -1, 1],
78            [0, 5, 0],
79            [1, 5, 1],
80            [2, 5, -1],
81            [-2, 5, -1],
82            [2, -5, -1],
83            [-2, -5, 1],
84            [3, 5, -1],
85            [5, 5, 0],
86            [-5, 5, 0],
87            [6, 5, 1],
88            [6, -5, 1],
89            [-6, 5, 1],
90            [-6, -5, -1],
91        ];
92
93        for case in cases.iter() {
94            let x = BigInt::from_i64(case[0]).unwrap();
95            let y = BigInt::from_i64(case[1]).unwrap();
96
97            assert_eq!(case[2] as isize, jacobi(&x, &y), "jacobi({}, {})", x, y);
98        }
99    }
100}
num_bigint_dig/algorithms/jacobi.rs

num_bigint_dig/algorithms/
jacobi.rs
