# (wrong string) ée

From: <git_AT_suckless.org>
Date: Mon, 25 Jul 2016 16:57:13 +0200 (CEST)

commit 243a542dce0f8da6fc3ac43d5e5fcb144559b507
Author: Mattias Andrée <maandree_AT_kth.se>
AuthorDate: Mon Jul 25 15:40:04 2016 +0200
Commit: Mattias Andrée <maandree_AT_kth.se>
CommitDate: Mon Jul 25 15:41:03 2016 +0200

Manual: how to calculate the legendre symbol

Signed-off-by: Mattias Andrée <maandree_AT_kth.se>

diff --git a/doc/not-implemented.tex b/doc/not-implemented.tex
index 586c2a8..27a03d5 100644
--- a/doc/not-implemented.tex
+++ b/doc/not-implemented.tex
_AT_@ -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}
Received on Mon Jul 25 2016 - 16:57:13 CEST

This archive was generated by hypermail 2.3.0 : Mon Jul 25 2016 - 17:00:19 CEST