Jacobi symbol
English[edit]
Etymology[edit]
Named after German mathematician Carl Gustav Jakob Jacobi, who introduced the notation in 1837.
Noun[edit]
Jacobi symbol (plural Jacobi symbols)
- (number theory) A mathematical function of integer a and odd positive integer b, generally written , based on, for each of the prime factors p_{i} of b, whether a is a quadratic residue or nonresidue modulo p_{i}.
- 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.
- 2009, Antoine Joux, Chapter 1: Introduction to Identity-Based Cryptography, Marc Joye, Gregory Neven (editors), Identity-based Cryptography, IOS Press, page 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.
- 2000, Song Y. Yan, Number Theory for Computing, Springer, 2000, Softcover reprint, page 114,
Usage notes[edit]
The value is defined as the product of Legendre symbols: if is the prime factorisation of b, then
- .
See also[edit]
Further reading[edit]
- Jacobi symbol on Wikipedia.Wikipedia
- Kronecker symbol on Wikipedia.Wikipedia