Editing Legendre symbol (section)

== Computational example ==
The above properties, including the law of quadratic reciprocity, can be used to evaluate any Legendre symbol. For example:

:<math>\begin{align}
\left ( \frac{12345}{331}\right )&=\left ( \frac{3}{331}\right ) \left ( \frac{5}{331}\right ) \left ( \frac{823}{331}\right ) \\
&= \left ( \frac{3}{331}\right ) \left ( \frac{5}{331}\right ) \left ( \frac{161}{331}\right ) \\
&= \left ( \frac{3}{331}\right ) \left ( \frac{5}{331}\right ) \left ( \frac{7}{331}\right ) \left ( \frac{23}{331}\right ) \\
&= (-1)\left (\frac{331}{3}\right) \left(\frac{331}{5}\right) (-1) \left(\frac{331}{7}\right) (-1)\left (\frac{331}{23}\right ) \\
&= -\left ( \frac{1}{3}\right ) \left ( \frac{1}{5}\right ) \left ( \frac{2}{7}\right ) \left ( \frac{9}{23}\right )\\
&= -\left ( \frac{1}{3}\right ) \left ( \frac{1}{5}\right ) \left ( \frac{2}{7}\right ) \left ( \frac{3^2}{23}\right )\\
&= -(1) (1) (1) (1) \\
&= -1.
\end{align}</math>

Or using a more efficient computation:
:<math>\left ( \frac{12345}{331}\right )=\left ( \frac{98}{331}\right )=\left ( \frac{2 \cdot 7^2}{331}\right )=\left ( \frac{2}{331}\right )=(-1)^\tfrac{331^2-1}{8}=-1.</math>
The article [[Jacobi symbol#Calculations using the Legendre symbol|Jacobi symbol]] has more examples of Legendre symbol manipulation.

Since no efficient [[Integer factorization|factorization]] algorithm is known, but efficient [[modular exponentiation]] algorithms are, in general it is more efficient to use Legendre's original definition, e.g.

:<math>\begin{align}
\left(\frac{98}{331}\right) &\equiv 98^{\frac{331-1}{2}} &\pmod{331} \\
&\equiv 98^{165} &\pmod{331} \\
&\equiv 98 \cdot (98^2)^{82} &\pmod{331} \\
&\equiv 98 \cdot 5^{82} &\pmod{331} \\
&\equiv 98 \cdot 25^{41} &\pmod{331} \\
&\equiv 133 \cdot 25^{40} &\pmod{331} \\
&\equiv 133 \cdot 294^{20} &\pmod{331} \\
&\equiv 133 \cdot 45^{10} &\pmod{331} \\
&\equiv 133 \cdot 39^5 &\pmod{331} \\
&\equiv 222 \cdot 39^4 &\pmod{331} \\
&\equiv 222 \cdot 197^2 &\pmod{331} \\
&\equiv 222 \cdot 82 &\pmod{331} \\
&\equiv -1 &\pmod{331}
\end{align}</math>

using [[repeated squaring]] modulo 331, reducing every value using the modulus after every operation to avoid computation with large integers.