Alternative solution for [20] Fast primality test with bounded perfection - libzahl - big integer library
HTML git clone git://git.suckless.org/libzahl
DIR Log
DIR Files
DIR Refs
DIR README
DIR LICENSE
---
DIR commit 63bc4e141d2f28fcd11187413966235151a92c84
DIR parent 076e4e3284039e1229bc7f99232e415cdc44711d
HTML Author: Mattias Andrée <maandree@kth.se>
Date: Mon, 25 Jul 2016 01:33:10 +0200
Alternative solution for [20] Fast primality test with bounded perfection
Signed-off-by: Mattias Andrée <maandree@kth.se>
Diffstat:
M doc/exercises.tex | 9 +++++++++
1 file changed, 9 insertions(+), 0 deletions(-)
---
DIR diff --git 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}