Jacobi symbol

English

Etymology

Named after German mathematician Template:W, who introduced the notation in 1837.

Noun

1. Template:Lb A mathematical function of integer a and odd positive integer b, generally written $\left(\frac{a}{b}\right)$, 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 $\left(\frac{1009}{2307}\right)=1$, we still cannot determine whether or not the quadratic congruence $1009=x^2(\mathrm{mod}2307)$ is soluble.

     Remark 1.6.10. Jacobi symbols can be used to facilitate the calculation of Legendre symbols.

   • Template:Quote-book
   • 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 $\left(\frac{2y_i{s}_{j_1}{s}_{j_2}+2}{N}\right)$ from $\left(\frac{2y_{j_1}{s}_{j_1}+2}{N}\right)$ and $\left(\frac{2y_{j_2}{s}_{j_2}+2}{N}\right)$ is as hard as guessing them from independent Jacobi symbols.

Usage notes

The value is defined as the product of Legendre symbols: if $b=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_k^{{\alpha }_k}$ is the prime factorisation of b, then

$\left(\frac{a}{b}\right)={\left(\frac{a}{p_1}\right)}^{{\alpha }_1}{\left(\frac{a}{p_2}\right)}^{{\alpha }_2}\cdots {\left(\frac{a}{p_k}\right)}^{{\alpha }_k}$.

See also

• Template:L
• Template:L

Further reading

• Template:Pedia
• Template:Pedia