- 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:13:40 +0200 (CEST)

commit 076e4e3284039e1229bc7f99232e415cdc44711d

Author: Mattias Andrée <maandree_AT_kth.se>

AuthorDate: Mon Jul 25 01:13:00 2016 +0200

Commit: Mattias Andrée <maandree_AT_kth.se>

CommitDate: Mon Jul 25 01:13:00 2016 +0200

Add exercise: [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 46fa6dd..7f9d7c8 100644

--- a/doc/exercises.tex

+++ b/doc/exercises.tex

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

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

Received on Mon Jul 25 2016 - 01:13:40 CEST

Date: Mon, 25 Jul 2016 01:13:40 +0200 (CEST)

commit 076e4e3284039e1229bc7f99232e415cdc44711d

Author: Mattias Andrée <maandree_AT_kth.se>

AuthorDate: Mon Jul 25 01:13:00 2016 +0200

Commit: Mattias Andrée <maandree_AT_kth.se>

CommitDate: Mon Jul 25 01:13:00 2016 +0200

Add exercise: [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 46fa6dd..7f9d7c8 100644

--- a/doc/exercises.tex

+++ b/doc/exercises.tex

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

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

Received on Mon Jul 25 2016 - 01:13:40 CEST

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