From 243a542dce0f8da6fc3ac43d5e5fcb144559b507 Mon Sep 17 00:00:00 2001 From: Mattias Andrée Date: Mon, 25 Jul 2016 15:40:04 +0200 Subject: Manual: how to calculate the legendre symbol MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Signed-off-by: Mattias Andrée --- doc/not-implemented.tex | 18 +++++++++++++++++- 1 file changed, 17 insertions(+), 1 deletion(-) (limited to 'doc/not-implemented.tex') 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 @@ -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} -- cgit v1.2.3-70-g09d2