From 243a542dce0f8da6fc3ac43d5e5fcb144559b507 Mon Sep 17 00:00:00 2001
From: Mattias Andrée <maandree@kth.se>
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 <maandree@kth.se>
---
 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

