libzahl

big integer library
git clone git://git.suckless.org/libzahl

commit 019da3a9e7f81cd882d0383ac707ce098013b4a9
parent 60dd5110e21d1aedc047f2033af74330df552e40
Author: Mattias Andrée <maandree@kth.se>
Date:   Mon, 25 Jul 2016 16:38:43 +0200

Manual: The Kronecker symbol

Signed-off-by: Mattias Andrée <maandree@kth.se>

Diffstat:
 M doc/not-implemented.tex | 60 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++----
1 file changed, 56 insertions(+), 4 deletions(-)

diff --git a/doc/not-implemented.tex b/doc/not-implemented.tex @@ -163,7 +163,8 @@ so a compressed lookup table can be used for small $p$. \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}$. +where $\displaystyle{n = \prod_k p_k^{n_k} > 0}$, +and $p_k \in \textbf{P}$. \vspace{1em} Like the Legendre symbol, the Jacobi symbol is $n$-period over $a$. @@ -197,14 +198,65 @@ Use the following algorithm to calculate the Jacobi symbol: \STATE \textbf{start over} \end{algorithmic} \end{minipage} -\vspace{1em} - \subsection{Kronecker symbol} \label{sec:Kronecker symbol} -TODO +The Kronecker symbol +$\displaystyle{\left ( \frac{a}{n} \right )}$ +is a generalisation of the Jacobi symbol, +where $n$ can be any integer. For positive +odd $n$, the Kronecker symbol is equal to +the Jacobi symbol. For even $n$, the +Kronecker symbol is $2n$-periodic over $a$, +the Kronecker symbol is zero for all +$(a, n)$ with both $a$ and $n$ are even. + +\vspace{1em} +\noindent +$$\displaystyle{ + \left ( \frac{a}{2^k \cdot n} \right ) = + \left ( \frac{a}{n} \right ) \cdot \left ( \frac{a}{2} \right )^k, +}$$ +where +$$\displaystyle{ + \left ( \frac{a}{2} \right ) = + \left \lbrace \begin{array}{rl} + 1 & \text{if}~ a \equiv 1, 7 ~(\text{Mod}~ 8) \\ + -1 & \text{if}~ a \equiv 3, 5 ~(\text{Mod}~ 8) \\ + 0 & \text{otherwise} + \end{array} \right . +}$$ + +\vspace{1em} +\noindent +$$\displaystyle{ + \left ( \frac{-a}{n} \right ) = + \left ( \frac{a}{n} \right ) \cdot \left ( \frac{a}{-1} \right ), +}$$ +where +$$\displaystyle{ + \left ( \frac{a}{-1} \right ) = + \left \lbrace \begin{array}{rl} + 1 & \text{if}~ a \ge 0 \\ + -1 & \text{if}~ a < 0 + \end{array} \right . +}$$ +\vspace{1em} + +\noindent +However, for $n = 0$, the symbol is defined as + +\vspace{1em} +\noindent +$$\displaystyle{ + \left ( \frac{a}{0} \right ) = + \left \lbrace \begin{array}{rl} + 1 & \text{if}~ a = \pm 1 \\ + 0 & \text{otherwise.} + \end{array} \right . +}$$ \subsection{Power residue symbol}