[hackers] [libzahl] Alternative solution for [20] Fast primality test with bounded perfection || Mattias Andrée

[git]

commit 63bc4e141d2f28fcd11187413966235151a92c84
Author:     Mattias Andrée <maand...@kth.se>
AuthorDate: Mon Jul 25 01:33:10 2016 +0200
Commit:     Mattias Andrée <maand...@kth.se>
CommitDate: Mon Jul 25 01:33:10 2016 +0200

    Alternative solution for [20] Fast primality test with bounded perfection
    
    Signed-off-by: Mattias Andrée <maand...@kth.se>

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}