libzahl

commit ccc36c882dc899ce75e41c7675ce48263ad24bfa
parent 555b57b3190c2ed6f73970c0515ac77dc4087220
Author: Mattias Andrée <maandree@kth.se>
Date:   Sun, 24 Jul 2016 03:58:08 +0200

Add exercise: [05] Fast primality test

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

Diffstat:
M
doc/exercises.tex
 | 
37
+++++++++++++++++++++++++++++++++++++

1 file changed, 37 insertions(+), 0 deletions(-)
diff --git 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}