From 076e4e3284039e1229bc7f99232e415cdc44711d Mon Sep 17 00:00:00 2001 From: Mattias Andrée Date: Mon, 25 Jul 2016 01:13:00 +0200 Subject: Add exercise: [20] Fast primality test with bounded perfection MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Signed-off-by: Mattias Andrée --- doc/exercises.tex | 36 ++++++++++++++++++++++++++++++++++++ 1 file changed, 36 insertions(+) (limited to 'doc') diff --git a/doc/exercises.tex b/doc/exercises.tex index 46fa6dd..7f9d7c8 100644 --- 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} -- cgit v1.2.3-70-g09d2