libzahl

big integer library
git clone git://git.suckless.org/libzahl
Log | Files | Refs | README | LICENSE

commit d067895614aed8572f40da22ccea50b781cfbc0d
parent fd9c83cbb9d80a8108cd5112d12f475406b44a20
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:
doc/arithmetic.tex | 18++++++------------
doc/not-implemented.tex | 18+++++++++---------
doc/number-theory.tex | 96++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++---------
3 files changed, 100 insertions(+), 32 deletions(-)

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 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} }\) 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}.