- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: <git_AT_suckless.org>

Date: Mon, 25 Jul 2016 01:33:54 +0200 (CEST)

commit 63bc4e141d2f28fcd11187413966235151a92c84

Author: Mattias Andrée <maandree_AT_kth.se>

AuthorDate: Mon Jul 25 01:33:10 2016 +0200

Commit: Mattias Andrée <maandree_AT_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 <maandree_AT_kth.se>

diff --git a/doc/exercises.tex b/doc/exercises.tex

index 7f9d7c8..cebff1c 100644

--- a/doc/exercises.tex

+++ b/doc/exercises.tex

_AT_@ -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}

Received on Mon Jul 25 2016 - 01:33:54 CEST

Date: Mon, 25 Jul 2016 01:33:54 +0200 (CEST)

commit 63bc4e141d2f28fcd11187413966235151a92c84

Author: Mattias Andrée <maandree_AT_kth.se>

AuthorDate: Mon Jul 25 01:33:10 2016 +0200

Commit: Mattias Andrée <maandree_AT_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 <maandree_AT_kth.se>

diff --git a/doc/exercises.tex b/doc/exercises.tex

index 7f9d7c8..cebff1c 100644

--- a/doc/exercises.tex

+++ b/doc/exercises.tex

_AT_@ -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}

Received on Mon Jul 25 2016 - 01:33:54 CEST

*
This archive was generated by hypermail 2.3.0
: Mon Jul 25 2016 - 01:36:22 CEST
*