 |
Manual: how to calculate the legendre symbol - libzahl - big integer library |
 |
git clone git://git.suckless.org/libzahl |
 |
Log |
|
Files |
|
Refs |
|
README |
|
LICENSE |
|
--- |
|
commit 243a542dce0f8da6fc3ac43d5e5fcb144559b507 |
|
parent 802b2b18704f1b04ab3c3195d49333a546dc0ff4 |
|
Author: Mattias Andrée <[email protected]> |
|
Date: Mon, 25 Jul 2016 15:40:04 +0200 |
|
|
|
Manual: how to calculate the legendre symbol |
|
|
|
Signed-off-by: Mattias Andrée <[email protected]> |
|
|
|
Diffstat: |
|
M doc/not-implemented.tex | 18 +++++++++++++++++- |
|
|
|
1 file changed, 17 insertions(+), 1 deletion(-) |
|
--- |
|
diff --git a/doc/not-implemented.tex b/doc/not-implemented.tex |
|
@@ -136,7 +136,23 @@ TODO |
|
\subsection{Legendre symbol} |
|
\label{sec:Legendre symbol} |
|
|
|
-TODO |
|
+\( \displaystyle{ |
|
+ \left ( \frac{a}{p} \right ) \equiv a^{\frac{p - 1}{2}} ~(\text{Mod}~p),~ |
|
+ \left ( \frac{a}{p} \right ) \in \{-1,~0,~1\},~ |
|
+ p \in \textbf{P},~ p > 2 |
|
+}\) |
|
+ |
|
+\noindent |
|
+That is, unless $\displaystyle{a^{\frac{p - 1}{2}} ~\text{Mod}~ p \le 1}$, |
|
+$\displaystyle{a^{\frac{p - 1}{2}} ~\text{Mod}~ p = p - 1}$, so |
|
+$\displaystyle{\left ( \frac{a}{p} \right ) = -1}$. |
|
+ |
|
+It should be noted that |
|
+\( \displaystyle{ |
|
+ \left ( \frac{a}{p} \right ) = |
|
+ \left ( \frac{a ~\text{Mod}~ p}{p} \right ), |
|
+}\) |
|
+so a compressed lookup table can be used for small $p$. |
|
|
|
|
|
\subsection{Jacobi symbol} |
