Jacobi symbolとは 意味・読み方・使い方

名詞

Jacobi symbol (複数形 Jacobi symbols)

1. (number theory) A mathematical function of integer a and odd positive integer b, generally written ${\displaystyle \left({a \over 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 ${\displaystyle \left({\frac {1009}{2307}}\right)=1}$, we still cannot determine whether or not the quadratic congruence ${\displaystyle 1009=x^{2}{\pmod {2307}}}$ 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 ${\displaystyle \textstyle \left({\frac {2y_{i}s_{j_{1}}s_{j_{2}}+2}{N}}\right)}$ from ${\displaystyle \textstyle \left({\frac {2y_{j_{1}}s_{j_{1}}+2}{N}}\right)}$ and ${\displaystyle \textstyle \left({\frac {2y_{j_{2}}s_{j_{2}}+2}{N}}\right)}$ is as hard as guessing them from independent Jacobi symbols.

使用する際の注意点

The value is defined as the product of Legendre symbols: if ${\displaystyle b=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdots p_{k}^{\alpha _{k}}}$ is the prime factorisation of b, then

${\displaystyle \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}}}$.

参考

• Legendre symbol
• quadratic reciprocity

Further reading

• Jacobi symbol on Wikipedia.
• Kronecker symbol on Wikipedia.