Editing Jacobi symbol (section)

==Example of calculations==

The Legendre symbol {{big|(}}{{sfrac|''a''|''p''}}{{big|)}} is only defined for odd primes ''p''.  It obeys the same rules as the Jacobi symbol (i.e., reciprocity and the supplementary formulas for {{big|(}}{{sfrac|−1|''p''}}{{big|)}} and {{big|(}}{{sfrac|2|''p''}}{{big|)}} and multiplicativity of the "numerator".)

Problem: Given that 9907 is prime, calculate {{big|(}}{{sfrac|1001|9907}}{{big|)}}.

===Using the Legendre symbol===

:<math>\begin{align}
\left(\frac{1001}{9907}\right) 
&=\left(\frac{7}{9907}\right) \left(\frac{11}{9907}\right) \left(\frac{13}{9907}\right). 
\\
\left(\frac{7}{9907}\right) 
&=-\left(\frac{9907}{7}\right) 
=-\left(\frac{2}{7}\right) 
=-1.
\\
\left(\frac{11}{9907}\right) 
&=-\left(\frac{9907}{11}\right) 
=-\left(\frac{7}{11}\right) 
=\left(\frac{11}{7}\right) 
=\left(\frac{4}{7}\right)
=1.
\\
\left(\frac{13}{9907}\right) 
&=\left(\frac{9907}{13}\right) 
=\left(\frac{1}{13}\right)
=1.
\\
\left(\frac{1001}{9907}\right) &=-1. \end{align}</math>

===Using the Jacobi symbol===

:<math>\begin{align}
  \left(\frac{1001}{9907}\right) 
&=\left(\frac{9907}{1001}\right) 
 =\left(\frac{898}{1001}\right) 
 =\left(\frac{2}{1001}\right)\left(\frac{449}{1001}\right)
 =\left(\frac{449}{1001}\right)
\\
&=\left(\frac{1001}{449}\right) 
 =\left(\frac{103}{449}\right) 
 =\left(\frac{449}{103}\right) 
 =\left(\frac{37}{103}\right) 
 =\left(\frac{103}{37}\right) 
\\
&=\left(\frac{29}{37}\right)  
 =\left(\frac{37}{29}\right) 
 =\left(\frac{8}{29}\right) 
 =\left(\frac{2}{29}\right)^3 
 =-1.
\end{align}</math>

The difference between the two calculations is that when the Legendre symbol is used the "numerator" has to be factored into prime powers before the symbol is flipped. This makes the  calculation using the Legendre symbol significantly slower than the one using the Jacobi symbol, as there is no known polynomial-time algorithm for factoring integers.<ref>The [[General number field sieve|number field sieve]], the fastest known algorithm, requires
:<math>O\left(e^{(\ln N)^\frac13(\ln\ln N)^\frac23\big(C+o(1)\big)}\right)</math>
operations  to factor ''n''. See Cohen, p. 495</ref> In fact, this is why Jacobi introduced the symbol.