Add exercise: [05] Fast 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 ccc36c882dc899ce75e41c7675ce48263ad24bfa
DIR parent 555b57b3190c2ed6f73970c0515ac77dc4087220
HTML Author: Mattias Andrée <maandree@kth.se>
Date: Sun, 24 Jul 2016 03:58:08 +0200
Add exercise: [05] Fast primality test
Signed-off-by: Mattias Andrée <maandree@kth.se>
Diffstat:
M doc/exercises.tex | 37 +++++++++++++++++++++++++++++++
1 file changed, 37 insertions(+), 0 deletions(-)
---
DIR diff --git a/doc/exercises.tex b/doc/exercises.tex
@@ -36,6 +36,7 @@ where $L_n$ is the $n^{\text{th}}$ Lucas Number \psecref{sec:Lucas numbers}.
}\)
+
\item {[\textit{M12${}^+$}]} \textbf{Factorisation of factorials}
Implement the function
@@ -52,6 +53,7 @@ The function shall be efficient for all $n$ where all primes $p \le n$ can
be found efficiently. You can assume that $n \ge 2$. You should not evaluate $n!$.
+
\item {[\textit{M20}]} \textbf{Reverse factorisation of factorials}
You should already have solved ``Factorisation of factorials''
@@ -73,6 +75,15 @@ $\displaystyle{\prod_{i = 1}^{n} P_i^{K_i}}$, where
$P_i$ is \texttt{P[i - 1]} and $K_i$ is \texttt{K[i - 1]}.
+
+\item {[\textit{05}]} \textbf{Fast primality test}
+
+$(x + y)^p \equiv x^p + y^p ~(\text{Mod}~p)$
+for all primes $p$ and for a few composites $p$.
+Use this to implement a fast primality tester.
+
+
+
\end{enumerate}
@@ -101,6 +112,7 @@ $$ 1 + \varphi = \frac{1}{\varphi} $$
So the ratio tends toward the golden ratio.
+
\item \textbf{Factorisation of factorials}
Base your implementation on
@@ -114,6 +126,7 @@ There is no need to calculate $\lfloor \log_p n \rfloor$,
you will see when $p^a > n$.
+
\item \textbf{Reverse factorisation of factorials}
$\displaystyle{x = \max_{p ~\in~ P} ~ p \cdot f(p, k_p)}$,
@@ -140,4 +153,28 @@ of $x!$. $f(p, k)$ is defined as:
+\item \textbf{Fast primality test}
+
+If we select $x = y = 1$ we get $2^p \equiv 2 ~(\text{Mod}~p)$. This gives us
+
+\vspace{-1em}
+\begin{alltt}
+enum zprimality ptest_fast(z_t p)
+\{
+ z_t a;
+ int c = zcmpu(p, 2);
+ if (c <= 0)
+ return c ? NONPRIME : PRIME;
+ zinit(a);
+ zsetu(a, 1);
+ zlsh(a, a, p);
+ zmod(a, a, p);
+ c = zcmpu(a, 2);
+ zfree(a);
+ return c ? NONPRIME : PROBABLY_PRIME;
+\}
+\end{alltt}
+
+
+
\end{enumerate}