pub fn jacobi<const L: usize>(n: &[u64], d: &[u64]) -> i64Expand description
Returns the Jacobi symbol (“n” / “d”) computed by means of the modification of the the Pornin’s method for modular inversion. The arguments are unsigned big integers in the form of arrays of 64-bit chunks, the ordering of which is little-endian. The value of “d” must be odd in accordance with the Jacobi symbol definition. Both the arguments must be less than 2 ^ (64 * L - 31). For an incorrect input, the behavior of the function is undefined. The method differs from the Pornin’s method for modular inversion in absence of the parts, which are not necessary to compute the greatest common divisor of arguments, presence of the parts used to compute the Jacobi symbol, which are based on the properties of the modified Jacobi symbol (x / |y|) described by M. Hamburg, and some original optimizations. Only these differences have been commented; the aforesaid Pornin’s method and the used ideas of M. Hamburg were given here:
- T. Pornin, “Optimized Binary GCD for Modular Inversion”, https://eprint.iacr.org/2020/972.pdf
- M. Hamburg, “Computing the Jacobi symbol using Bernstein-Yang”, https://eprint.iacr.org/2021/1271.pdf