Add exercises: [10] Fermat primality test - libzahl - big integer library
HTML git clone git://git.suckless.org/libzahl
DIR Log
DIR Files
DIR Refs
DIR README
DIR LICENSE
---
DIR commit 4d41ca9124a0bbb4a26a856c76943317653ebc77
DIR parent ae8fb895ff82b75f7708b89c60565a2347e4593f
HTML Author: Mattias Andrée <maandree@kth.se>
Date: Sun, 24 Jul 2016 21:45:58 +0200
Add exercises: [10] Fermat primality test
Signed-off-by: Mattias Andrée <maandree@kth.se>
Diffstat:
M doc/exercises.tex | 60 +++++++++++++++++++++++++++++++
1 file changed, 60 insertions(+), 0 deletions(-)
---
DIR diff --git a/doc/exercises.tex b/doc/exercises.tex
@@ -130,6 +130,19 @@ a fast primality tester.
+\item {[\textit{10}]} \textbf{Fermat primality test}
+
+$a^{p - 1} \equiv 1 ~(\text{Mod}~p) ~\forall~ 1 < a < p$
+for all primes $p$ and for a few composites $p$,
+which are know as pseudoprimes\footnote{If $p$ is composite
+but passes the test for all $a$, $p$ is a Carmichael
+number.}. Use this to implement a heuristic primality
+tester. Try to mimic \texttt{zptest} as much as possible.
+GNU~MP uses $a = 210$, but you don't have to. ($a$ is
+called a base.)
+
+
+
\end{enumerate}
@@ -288,4 +301,51 @@ enum zprimality ptest_fast(z_t p)
+\item \textbf{Fermat primality test}
+
+Below is a simple implementation. It can be improved by
+just testing against a fix base, such as $a = 210$, it
+$t = 0$. It could also do an exhaustive test (all $a$
+such that $1 < a < p$) if $t < 0$.
+
+\vspace{-1em}
+\begin{alltt}
+enum zprimality ptest_fermat(z_t witness, z_t p, int t)
+\{
+ enum zprimality rc = PROBABLY_PRIME;
+ z_t a, p1, p3, temp;
+ int c;
+
+ if ((c = zcmpu(p, 2)) <= 0) \{
+ if (!c)
+ return PRIME;
+ if (witness && witness != p)
+ zset(witness, p);
+ return NONPRIME;
+ \}
+
+ zinit(a), zinit(p1), zinit(p3), zinit(temp);
+ zsetu(temp, 3), zsub(p3, p, temp);
+ zsetu(temp, 1), zsub(p1, p, temp);
+
+ zsetu(temp, 2);
+ while (t--) \{
+ zrand(a, DEFAULT_RANDOM, UNIFORM, p3);
+ zadd(a, a, temp);
+ zmodpow(a, a, p1, p);
+ if (zcmpu(a, 1)) \{
+ if (witness)
+ zswap(witness, a);
+ rc = NONPRIME;
+ break;
+ \}
+ \}
+
+ zfree(temp), zfree(p3), zfree(p1), zfree(a);
+ return rc;
+\}
+\end{alltt}
+
+
+
\end{enumerate}