Jacobi symbol

English Etymology Named after German mathematician Carl Gustav Jakob Jacobi, who introduced the notation in 1837. Noun en number theory A mathematical function of integer a and odd positive integer b, generally written , based on, for each of the prime factors pi of b, whether a is a quadratic residue or nonresidue modulo pi. 2000, Song Y. Yan, Number Theory for Computing, Springer, 2000, Softcover reprint, page 114, Although the Jacobi symbol , we still cannot determine whether or not the quadratic congruence is soluble. Remark 1.6.10. Jacobi symbols can be used to facilitate the calculation of Legendre symbols. en 2009 Antoine Joux Chapter 1: Introduction to Identity-Based Cryptography Marc Joye; Gregory Neven Identity-based Cryptography w:IOS Press https://books.google.com.au/books?id=6utNZkI-oGkC&pg=PA8&dq=%22Jacobi+symbol%22%7C%22Jacobi+symbols%22&hl=en&sa=X&ved=0ahUKEwiA8uO__uzWAhWIvrwKHbzSCnIQ6AEIPjAE#v=onepage&q=%22Jacobi%20symbol%22%7C%22Jacobi%20symbols%22&f=false 8 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 from and is as hard as guessing them from independent Jacobi symbols. Usage notes The value is defined as the product of Legendre symbols: if is the prime factorisation of b, then . See also en Legendre symbol en quadratic reciprocity Further reading Kronecker symbol en eponyms