From 63bc4e141d2f28fcd11187413966235151a92c84 Mon Sep 17 00:00:00 2001 From: Mattias Andrée Date: Mon, 25 Jul 2016 01:33:10 +0200 Subject: Alternative solution for [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 | 9 +++++++++ 1 file changed, 9 insertions(+) diff --git a/doc/exercises.tex b/doc/exercises.tex index 7f9d7c8..cebff1c 100644 --- a/doc/exercises.tex +++ b/doc/exercises.tex @@ -467,6 +467,15 @@ For input, larger than our limit, that passes the test, we can run it through \texttt{zptest} to reduce the number of false positives. +As an alternative solution, instead of comparing against +known pseudoprimes. Find a minimal set of primes that +includes divisors for all known pseudoprimes, and do +trail division with these primes when a number passes +the test. No pseudoprime need to have more than one divisor +included in the set, so this set cannot be larger than +the set of pseudoprimes. + + \end{enumerate} -- cgit v1.2.3-70-g09d2