(wrong string) ée

From: <git_AT_suckless.org>
Date: Mon, 25 Jul 2016 01:13:40 +0200 (CEST)

commit 076e4e3284039e1229bc7f99232e415cdc44711d
Author: Mattias Andrée <maandree_AT_kth.se>
AuthorDate: Mon Jul 25 01:13:00 2016 +0200
Commit: Mattias Andrée <maandree_AT_kth.se>
CommitDate: Mon Jul 25 01:13:00 2016 +0200

    Add exercise: [20] Fast primality test with bounded perfection
    
    Signed-off-by: Mattias Andrée <maandree_AT_kth.se>

diff --git a/doc/exercises.tex b/doc/exercises.tex
index 46fa6dd..7f9d7c8 100644
--- a/doc/exercises.tex
+++ b/doc/exercises.tex
_AT_@ -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}
 
 
_AT_@ -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}
Received on Mon Jul 25 2016 - 01:13:40 CEST