On primality test, and style - libzahl - big integer library
HTML git clone git://git.suckless.org/libzahl
DIR Log
DIR Files
DIR Refs
DIR README
DIR LICENSE
---
DIR commit d067895614aed8572f40da22ccea50b781cfbc0d
DIR parent fd9c83cbb9d80a8108cd5112d12f475406b44a20
HTML Author: Mattias Andrée <maandree@kth.se>
Date: Fri, 13 May 2016 20:40:05 +0200
On primality test, and style
Signed-off-by: Mattias Andrée <maandree@kth.se>
Diffstat:
M doc/arithmetic.tex | 18 ++++++------------
M doc/not-implemented.tex | 18 +++++++++---------
M doc/number-theory.tex | 96 +++++++++++++++++++++++++++----
3 files changed, 100 insertions(+), 32 deletions(-)
---
DIR diff --git a/doc/arithmetic.tex b/doc/arithmetic.tex
@@ -187,7 +187,7 @@ can be expressed as a simple formula
\vspace{-1em}
\[ \hspace*{-0.4cm}
a^b =
- \prod_{k \in \textbf{Z}_{+} ~:~ \left \lfloor {b \over 2^k} \hspace*{-1ex} \mod 2 \right \rfloor = 1}
+ \prod_{k \in \textbf{Z}_{+} ~:~ \left \lfloor \frac{b}{2^k} \hspace*{-1ex} \mod 2 \right \rfloor = 1}
a^{2^k}
\]
@@ -212,13 +212,10 @@ The algorithm can be expressed in psuedocode as
\hspace{-2.8ex}
\begin{minipage}{\linewidth}
\begin{algorithmic}
- \STATE $r \gets 1$
- \STATE $f \gets a$
+ \STATE $r, f \gets 1, a$
\WHILE{$b \neq 0$}
- \IF{$b \equiv 1 ~(\textrm{Mod}~ 2)$}
- \STATE $r \gets r \cdot f$
- \ENDIF
- \STATE $f \gets f^2$ \qquad \textcolor{c}{\{$f \gets f \cdot f$\}}
+ \STATE $r \gets r \cdot f$ {\bf unless} $2 \vert b$
+ \STATE $f \gets f^2$ \textcolor{c}{\{$f \gets f \cdot f$\}}
\STATE $b \gets \lfloor b / 2 \rfloor$
\ENDWHILE
\RETURN $r$
@@ -234,12 +231,9 @@ expressed as
\hspace{-2.8ex}
\begin{minipage}{\linewidth}
\begin{algorithmic}
- \STATE $r \gets 1$
- \STATE $f \gets a$
+ \STATE $r, f \gets 1, a$
\WHILE{$b \neq 0$}
- \IF{$b \equiv 1 ~(\textrm{Mod}~ 2)$}
- \STATE $r \gets r \cdot f \hspace*{-1ex}~ \mod m$
- \ENDIF
+ \STATE $r \gets r \cdot f \hspace*{-1ex}~ \mod m$ \textbf{unless} $2 \vert b$
\STATE $f \gets f^2 \hspace*{-1ex}~ \mod m$
\STATE $b \gets \lfloor b / 2 \rfloor$
\ENDWHILE
DIR diff --git a/doc/not-implemented.tex b/doc/not-implemented.tex
@@ -60,7 +60,7 @@ extgcd(z_t bézout_coeff_1, z_t bézout_coeff_2, z_t gcd
\label{sec:Least common multiple}
\( \displaystyle{
- \mbox{lcm}(a, b) = {\lvert a \cdot b \rvert \over \mbox{gcd}(a, b)}
+ \mbox{lcm}(a, b) = \frac{\lvert a \cdot b \rvert}{\mbox{gcd}(a, b)}
}\)
@@ -233,7 +233,7 @@ The resulting algorithm can be expressed
1 & \textrm{if}~ n = 0 \\
\textrm{undefined} & \textrm{otherwise}
\end{array} \right . =
- n! \sum_{i = 0}^n {(-1)^i \over i!}
+ n! \sum_{i = 0}^n \frac{(-1)^i}{i!}
}\)
@@ -286,7 +286,7 @@ The resulting algorithm can be expressed
\label{sec:Raising factorial}
\( \displaystyle{
- x^{(n)} = {(x + n - 1)! \over (x - 1)!}
+ x^{(n)} = \frac{(x + n - 1)!}{(x - 1)!}
}\), undefined for $n < 0$.
@@ -294,7 +294,7 @@ The resulting algorithm can be expressed
\label{sec:Falling factorial}
\( \displaystyle{
- (x)_n = {x! \over (x - n)!}
+ (x)_n = \frac{x!}{(x - n)!}
}\), undefined for $n < 0$.
@@ -334,9 +334,9 @@ $\Gamma(n) = (n - 1)!$, undefined for $n \le 0$.
\label{sec:Binomial coefficient}
\( \displaystyle{
- {n \choose k} = {n! \over k!(n - k)!}
- = {1 \over (n - k)!} \prod_{i = k + 1}^n i
- = {1 \over k!} \prod_{i = n - k + 1}^n i
+ \binom{n}{k} = \frac{n!}{k!(n - k)!}
+ = \frac{1}{(n - k)!} \prod_{i = k + 1}^n i
+ = \frac{1}{k!} \prod_{i = n - k + 1}^n i
}\)
@@ -344,7 +344,7 @@ $\Gamma(n) = (n - 1)!$, undefined for $n \le 0$.
\label{sec:Catalan number}
\( \displaystyle{
- C_n = \left . {2n \choose n} \middle / (n + 1) \right .
+ C_n = \left . \binom{2n}{n} \middle / (n + 1) \right .
}\)
@@ -352,7 +352,7 @@ $\Gamma(n) = (n - 1)!$, undefined for $n \le 0$.
\label{sec:Fuss-Catalan number} % not en dash
\( \displaystyle{
- A_m(p, r) = {r \over mp + r} {mp + r \choose m}
+ A_m(p, r) = \frac{r}{mp + r} \binom{mp + r}{m}
}\)
DIR diff --git a/doc/number-theory.tex b/doc/number-theory.tex
@@ -132,7 +132,7 @@ definion ensures
\vspace{1em}
\( \displaystyle{
- {a \over \gcd(a, b)} \left \lbrace \begin{array}{rl}
+ \frac{a}{\gcd(a, b)} \left \lbrace \begin{array}{rl}
> 0 & \textrm{if}~ a < 0, b < 0 \\
< 0 & \textrm{if}~ a < 0, b > 0 \\
= 1 & \textrm{if}~ b = 0, a \neq 0 \\
@@ -143,7 +143,7 @@ definion ensures
\vspace{1em}
\noindent
-and analogously for $b \over \gcd(a,\,b)$. Note however,
+and analogously for $\frac{b}{\gcd(a,\,b)}$. Note however,
the convension $\gcd(0, 0) = 0$ is adhered. Therefore,
before dividing with $\gcd{a, b}$ you may want to check
whether $\gcd(a, b) = 0$. $\gcd(a, b)$ is calculated
@@ -156,17 +156,12 @@ the Binary GCD algorithm.
\hspace{-2.8ex}
\begin{minipage}{\linewidth}
\begin{algorithmic}
- \IF{$ab = 0$}
- \RETURN $a + b$
- \ELSIF{$a < 0$ \AND $b < 0$}
- \RETURN $-\gcd(\lvert a \rvert, \lvert b \rvert)$
- \ENDIF
+ \RETURN $a + b$ {\bf if} $ab = 0$
+ \RETURN $-\gcd(\lvert a \rvert, \lvert b \rvert)$ {\bf if} $a < 0$ \AND $b < 0$
\STATE $s \gets \max s : 2^s \vert a, b$
\STATE $u, v \gets \lvert a \rvert \div 2^s, \lvert b \rvert \div 2^s$
\WHILE{$u \neq v$}
- \IF{$u > v$}
- \STATE $u \leftrightarrow v$
- \ENDIF
+ \STATE $v \leftrightarrow u$ {\bf if} $v < u$
\STATE $v \gets v - u$
\STATE $v \gets v \div 2^x$, where $x = \max x : 2^x \vert v$
\ENDWHILE
@@ -184,4 +179,83 @@ $\max x : 2^x \vert z$ is returned by {\tt zlsb(z)}
\section{Primality test}
\label{sec:Primality test}
-TODO % zptest
+The primality of an integer can be test with
+
+\begin{alltt}
+ enum zprimality zptest(z_t w, z_t a, int t);
+\end{alltt}
+
+\noindent
+{\tt zptest} uses Miller–Rabin primality test,
+with {\tt t} runs of its witness loop, to
+determine whether {\tt a} is prime. {\tt zptest}
+returns either
+
+\begin{itemize}
+\item {\tt PRIME} = 2:
+{\tt a} is prime. This is only returned for
+known prime numbers: 2 and 3.
+
+\item {\tt PROBABLY\_PRIME} = 1:
+{\tt a} is probably a prime. The certainty
+will be $1 - 4^{-t}$.
+
+\item {\tt NONPRIME} = 0:
+{\tt a} is either composite, non-positive, or 1.
+It is certain that {\tt a} is not prime.
+\end{itemize}
+
+If and only if {\tt NONPRIME} is returned, a
+value will be assigned to {\tt w} — unless
+{\tt w} is {\tt NULL}. This will be the witness
+of {\tt a}'s completeness. If $a \le 2$, it
+is not really composite, and the value of
+{\tt a} is copied into {\tt w}.
+
+$\gcd(w, a)$ can be used to extract a factor
+of $a$. This factor is however not necessarily,
+and unlikely so, prime, but can be composite,
+or even 1. In the latter case this becomes
+utterly useless, and therefore using this
+method for prime factorisation is a bad idea.
+
+Below is pseudocode for the Miller–Rabin primality
+test with witness return.
+
+\vspace{1em}
+\hspace{-2.8ex}
+\begin{minipage}{\linewidth}
+\begin{algorithmic}
+ \RETURN NONPRIME ($w \gets a$) {\bf if} {$a \le 1$}
+ \RETURN PRIME {\bf if} {$a \le 3$}
+ \RETURN NONPRIME ($w \gets 2$) {\bf if} {$2 \vert a$}
+ \STATE $r \gets \max r : 2^r \vert (a - 1)$
+ \STATE $d \gets (a - 1) \div 2^r$
+ \STATE {\bf repeat} $t$ {\bf times}
+
+ \hspace{2ex}
+ \begin{minipage}{\linewidth}
+ \STATE $k \xleftarrow{\$} \textbf{Z}_{a - 2} \setminus \textbf{Z}_{2}$
+ \STATE $x \gets k^d \mod a$
+ \STATE {\bf continue} {\bf if} $x = 1$ \OR $x = a - 1$
+ \STATE {\bf repeat} $r$ {\bf times or until} $x = 1$ \OR $x = a - 1$
+
+ \hspace{2ex}
+ \begin{minipage}{\linewidth}
+ \vspace{-1ex}
+ \STATE $x \gets x^2 \mod a$
+ \end{minipage}
+ \vspace{-1.5em}
+ \STATE {\bf end repeat}
+ \STATE {\bf if} $x = 1$ {\bf return} NONPRIME ($w \gets k$)
+ \end{minipage}
+ \vspace{-0.8ex}
+ \STATE {\bf end repeat}
+ \RETURN PROBABLY PRIME
+\end{algorithmic}
+\end{minipage}
+\vspace{1em}
+
+\noindent
+$\max x : 2^x \vert z$ is returned by {\tt zlsb(z)}
+\psecref{sec:Boundary}.