libzahl

commit 611db6bdb6a5a08b628f571451a94a1147a0e16f
parent f2734fde832c3f45d0dc9350c561d4137a422788
Author: Mattias Andrée <maandree@kth.se>
Date:   Mon, 25 Jul 2016 00:50:52 +0200

Add exercise: [11] Lucas–Lehmer primality test

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

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

1 file changed, 85 insertions(+), 0 deletions(-)
diff --git a/doc/exercises.tex b/doc/exercises.tex
@@ -143,6 +143,43 @@ called a base.)
 
 
 
+\item {[\textit{11}]} \textbf{Lucas–Lehmer primality test}
+
+The Lucas–Lehmer primality test can be used to determine
+whether a Mersenne numbers $M_n = 2^n - 1$ is a prime (a
+Mersenne prime). $M_n$ is a prime if and only if
+$s_{n - 1} \equiv 0 ~(\text{Mod}~M_n)$, where
+
+\( \displaystyle{
+    s_i = \left \{ \begin{array}{ll}
+      4 & \text{if} ~ i = 0 \\
+      s_{i - 1}^2 - 2 & \text{otherwise}.
+    \end{array} \right .
+}\)
+
+\noindent
+The Lucas–Lehmer primality test requires that $n \ge 3$,
+however $M_2 = 2^2 - 1 = 3$ is a prime. Implement a version
+of the Lucas–Lehmer primality test that takes $n$ as the
+input. For some more fun, when you are done, you can
+implement a version that takes $M_n$ as the input.
+
+For improved performance, instead of using \texttt{zmod},
+you can use the recursive function
+%
+\( \displaystyle{
+    k ~\mbox{Mod}~ 2^n - 1 =
+    \left (
+      (k ~\mbox{Mod}~ 2^n) + \lfloor k \div 2^n \rfloor
+    \right ) ~\mbox{Mod}~ 2^n - 1,
+}\)
+%
+where $k ~\mbox{Mod}~ 2^n$ is efficiently calculated
+using \texttt{zand($k$, $2^n - 1$)}. (This optimisation
+is not part of the difficulty rating of this problem.)
+
+
+
 \end{enumerate}
 
 
@@ -348,4 +385,52 @@ enum zprimality ptest_fermat(z_t witness, z_t p, int t)
 
 
 
+\item \textbf{Lucas–Lehmer primality test}
+
+\vspace{-1em}
+\begin{alltt}
+enum zprimality ptest_llt(z_t n)
+\{
+    z_t s, M;
+    int c;
+    size_t p;
+
+    if ((c = zcmpu(n, 2)) <= 0)
+        return c ? NONPRIME : PRIME;
+
+    if (n->used > 1) \{
+        \textcolor{c}{/* \textrm{An optimised implementation would not need this} */}
+        errno = ENOMEM;
+        return (enum zprimality)(-1);
+    \}
+
+    zinit(s), zinit(M), zinit(2);
+
+    p = (size_t)(n->chars[0]);
+    zsetu(s, 1), zsetu(M, 0);
+    zbset(M, M, p, 1), zsub(M, M, s);
+    zsetu(s, 4);
+    zsetu(two, 2);
+
+    p -= 2;
+    while (p--) \{
+        zsqr(s, s);
+        zsub(s, s, two);
+        zmod(s, s, M);
+    \}
+    c = zzero(s);
+
+    zfree(two), zfree(M), zfree(s);
+    return c ? PRIME : NONPRIME;
+\}
+\end{alltt}
+
+$M_n$ is composite if $n$ is composite, therefore,
+if you do not expect prime-only values on $n$, the
+performance can be improve by using some other
+primality test (or this same test if $n$ is a
+Mersenne number) to first check that $n$ is prime.
+
+
+
 \end{enumerate}