Jacobi symbol

Definition from Wiktionary, the free dictionary
Jump to navigation Jump to search



Named after German mathematician Carl Gustav Jakob Jacobi, who introduced the notation in 1837.


Jacobi symbol (plural Jacobi symbols)

  1. (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.
    • 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.

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]