[hackers] [libzahl] Add exercise: [05] Fast primality test || Mattias Andrée

[git]

commit ccc36c882dc899ce75e41c7675ce48263ad24bfa
Author:     Mattias Andrée <maand...@kth.se>
AuthorDate: Sun Jul 24 03:58:08 2016 +0200
Commit:     Mattias Andrée <maand...@kth.se>
CommitDate: Sun Jul 24 04:01:37 2016 +0200

    Add exercise: [05] Fast primality test
    
    Signed-off-by: Mattias Andrée <maand...@kth.se>

diff --git a/doc/exercises.tex b/doc/exercises.tex
index 2d68130..d170bb9 100644
--- a/doc/exercises.tex
+++ b/doc/exercises.tex
@@ -36,6 +36,7 @@ where $L_n$ is the $n^{\text{th}}$ Lucas Number 
\psecref{sec:Lucas numbers}.
 }\)
 
 
+
 \item {[\textit{M12${}^+$}]} \textbf{Factorisation of factorials}
 
 Implement the function
@@ -52,6 +53,7 @@ The function shall be efficient for all $n$ where all primes 
$p \le n$ can
 be found efficiently. You can assume that $n \ge 2$. You should not evaluate 
$n!$.
 
 
+
 \item {[\textit{M20}]} \textbf{Reverse factorisation of factorials}
 
 You should already have solved ``Factorisation of factorials''
@@ -73,6 +75,15 @@ $\displaystyle{\prod_{i = 1}^{n} P_i^{K_i}}$, where
 $P_i$ is \texttt{P[i - 1]} and $K_i$ is \texttt{K[i - 1]}.
 
 
+
+\item {[\textit{05}]} \textbf{Fast primality test}
+
+$(x + y)^p \equiv x^p + y^p ~(\text{Mod}~p)$
+for all primes $p$ and for a few composites $p$.
+Use this to implement a fast primality tester.
+
+
+
 \end{enumerate}
 
 
@@ -101,6 +112,7 @@ $$ 1 + \varphi = \frac{1}{\varphi} $$
 So the ratio tends toward the golden ratio.
 
 
+
 \item \textbf{Factorisation of factorials}
 
 Base your implementation on
@@ -114,6 +126,7 @@ There is no need to calculate $\lfloor \log_p n \rfloor$,
 you will see when $p^a > n$.
 
 
+
 \item \textbf{Reverse factorisation of factorials}
 
 $\displaystyle{x = \max_{p ~\in~ P} ~ p \cdot f(p, k_p)}$,
@@ -140,4 +153,28 @@ of $x!$. $f(p, k)$ is defined as:
 
 
 
+\item \textbf{Fast primality test}
+
+If we select $x = y = 1$ we get $2^p \equiv 2 ~(\text{Mod}~p)$. This gives us
+
+\vspace{-1em}
+\begin{alltt}
+enum zprimality ptest_fast(z_t p)
+\{
+    z_t a;
+    int c = zcmpu(p, 2);
+    if (c <= 0)
+      return c ? NONPRIME : PRIME;
+    zinit(a);
+    zsetu(a, 1);
+    zlsh(a, a, p);
+    zmod(a, a, p);
+    c = zcmpu(a, 2);
+    zfree(a);
+    return c ? NONPRIME : PROBABLY_PRIME;
+\}
+\end{alltt}
+
+
+
 \end{enumerate}