Meaning of Jacobi symbol | Babel Free

Definitions

A mathematical function of integer a and odd positive integer b, generally written (a/b), based on, for each of the prime factors pᵢ of b, whether a is a quadratic residue or nonresidue modulo pᵢ.

Examples

“2000, Song Y. Yan, Number⟳ Theory for Computing, Springer, 2000, Softcover reprint, page 114, Although the Jacobi symbol ((1009)/(2307))=1, we still cannot determine⟳ whether or not the quadratic congruence 1009=x²(mod 2307) is soluble. Remark⟳ 1.6.10. Jacobi symbols can be used to facilitate the calculation of Legendre symbols.”

“With more than two factors, having a Jacobi symbol of 1 only means that x may be a quadratic non-residue modulo an even number⟳ of factors only. Thus in the general case, the Jacobi symbol is not enough to test⟳ for the existence of a discrete logarithm. Thanks to this efficient test⟳, given any public process⟳, for example based on a hash function, that transforms the identity of a user into a number⟳ x modulo N, this number⟳ can directly be used as the user's public key if its Jacobi symbol is 1.”

“2014, Ibrahim Elashry, Yi Mu, Willy Susilo, Jhanwar-Barua's Identity-Based Encryption Revisited, Man Ho Au, Barbara Carminati, C.-C. Jay Kuo (editors), Network and System Security: 8th International Conference, Springer, LNCS 8792, page 279, From the above equations, guessing the Jacobi symbol ((2y_is_j_1s_j_2+2)/N) from ((2y_j_1s_j_1+2)/N) and ((2y_j_2s_j_2+2)/N) is as hard as guessing them from independent Jacobi symbols.”

CEFR level