Manual: How to calculate the Jacobi symbol - libzahl - big integer library
HTML git clone git://git.suckless.org/libzahl
DIR Log
DIR Files
DIR Refs
DIR README
DIR LICENSE
---
DIR commit 60dd5110e21d1aedc047f2033af74330df552e40
DIR parent 4d2e79e7eec793a557c26d1253bcfc13f6b555d6
HTML Author: Mattias Andrée <maandree@kth.se>
Date: Mon, 25 Jul 2016 16:15:08 +0200
Manual: How to calculate the Jacobi symbol
Signed-off-by: Mattias Andrée <maandree@kth.se>
Diffstat:
M doc/not-implemented.tex | 46 +++++++++++++++++++++++++++++--
1 file changed, 43 insertions(+), 3 deletions(-)
---
DIR diff --git a/doc/not-implemented.tex b/doc/not-implemented.tex
@@ -141,10 +141,11 @@ TODO
\left ( \frac{a}{p} \right ) \in \{-1,~0,~1\},~
p \in \textbf{P},~ p > 2
}\)
+\vspace{1em}
\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
+That is, unless $\displaystyle{a^{\frac{p - 1}{2}} \mod p \le 1}$,
+$\displaystyle{a^{\frac{p - 1}{2}} \mod p = p - 1}$, so
$\displaystyle{\left ( \frac{a}{p} \right ) = -1}$.
It should be noted that
@@ -158,7 +159,46 @@ so a compressed lookup table can be used for small $p$.
\subsection{Jacobi symbol}
\label{sec:Jacobi symbol}
-TODO
+\( \displaystyle{
+ \left ( \frac{a}{n} \right ) =
+ \prod_k \left ( \frac{a}{p_k} \right )^{n_k},
+}\)
+where $n$ = $\displaystyle{\prod_k p_k^{n_k}}$, and $p_k \in \textbf{P}$.
+\vspace{1em}
+
+Like the Legendre symbol, the Jacobi symbol is $n$-period over $a$.
+If $n$, is prime, the Jacobi symbol is the Legendre symbol, but
+the Jacobi symbol is defined for all odd numbers $n$, where the
+Legendre symbol is defined only for odd primes $n$.
+
+Use the following algorithm to calculate the Jacobi symbol:
+
+\vspace{1em}
+\hspace{-2.8ex}
+\begin{minipage}{\linewidth}
+\begin{algorithmic}
+ \STATE $a \gets a \mod n$
+ \STATE $r \gets \mbox{lsb}~ a$
+ \STATE $a \gets a \cdot 2^{-r}$
+ \STATE \(\displaystyle{
+ r \gets \left \lbrace \begin{array}{rl}
+ 1 &
+ \text{if}~ n \equiv 1, 7 ~(\text{Mod}~ 8)
+ ~\text{or}~ r \equiv 0 ~(\text{Mod}~ 2) \\
+ -1 & \text{otherwise} \\
+ \end{array} \right .
+ }\)
+ \IF{$a = 1$}
+ \RETURN $r$
+ \ELSIF{$\gcd(a, n) \neq 1$}
+ \RETURN $0$
+ \ENDIF
+ \STATE $(a, n) = (n, a)$
+ \STATE \textbf{start over}
+\end{algorithmic}
+\end{minipage}
+\vspace{1em}
+
\subsection{Kronecker symbol}