libzahl

commit 076e4e3284039e1229bc7f99232e415cdc44711d
parent 611db6bdb6a5a08b628f571451a94a1147a0e16f
Author: Mattias Andrée <maandree@kth.se>
Date:   Mon, 25 Jul 2016 01:13:00 +0200

Add exercise: [20] Fast primality test with bounded perfection

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

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

1 file changed, 36 insertions(+), 0 deletions(-)
diff --git a/doc/exercises.tex b/doc/exercises.tex
@@ -180,6 +180,14 @@ is not part of the difficulty rating of this problem.)
 
 
 
+\item {[\textit{20}]} \textbf{Fast primality test with bounded perfection}
+
+Implement a primality test that is both very fast and
+never returns \texttt{PROBABLY\_PRIME} for input less
+than or equal to a preselected number.
+
+
+
 \end{enumerate}
 
 
@@ -433,4 +441,32 @@ Mersenne number) to first check that $n$ is prime.
 
 
 
+\item \textbf{Fast primality test with bounded perfection}
+
+First we select a fast primality test. We can use
+$2^p \equiv 2 ~(\texttt{Mod}~ p) ~\forall~ p \in \textbf{P}$,
+as describe in the solution for the problem
+\textit{Fast primality test}.
+
+Next, we use this to generate a large list of primes and
+pseudoprimes. Use a perfect primality test, such as a
+naïve test or the AKS primality test, to filter out all
+primes and retain only the pseudoprimes. This is not in
+runtime so it does not matter that this is slow, but to
+speed it up, we can use a probabilistic test such the
+Miller–Rabin primality test (\texttt{zptest}) before we
+use the perfect test.
+
+Now that we have a quite large — but not humongous — list
+of pseudoprimes, we can incorporate it into our fast
+primality test. For any input that passes the test, and
+is less or equal to the largest pseudoprime we found,
+binary search our list of pseudoprime for the input.
+
+For input, larger than our limit, that passes the test,
+we can run it through \texttt{zptest} to reduce the
+number of false positives.
+
+
+
 \end{enumerate}