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)

  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”, in 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