number-theory.tex - libzahl - big integer library
HTML git clone git://git.suckless.org/libzahl
DIR Log
DIR Files
DIR Refs
DIR README
DIR LICENSE
---
number-theory.tex (7238B)
---
1 \chapter{Number theory}
2 \label{chap:Number theory}
3
4 In this chapter, you will learn about the
5 number theoretic functions in libzahl.
6
7 \vspace{1cm}
8 \minitoc
9
10
11 \newpage
12 \section{Odd or even}
13 \label{sec:Odd or even}
14
15 There are four functions available for testing
16 the oddness and evenness of an integer:
17
18 \begin{alltt}
19 int zodd(z_t a);
20 int zeven(z_t a);
21 int zodd_nonzero(z_t a);
22 int zeven_nonzero(z_t a);
23 \end{alltt}
24
25 \noindent
26 {\tt zodd} returns 1 if {\tt a} contains an
27 odd value, or 0 if {\tt a} contains an even
28 number. Conversely, {\tt zeven} returns 1 if
29 {\tt a} contains an even value, or 0 if {\tt a}
30 contains an odd number. {\tt zodd\_nonzero} and
31 {\tt zeven\_nonzero} behave exactly like {\tt zodd}
32 and {\tt zeven}, respectively, but assumes that
33 {\tt a} contains a non-zero value, if not
34 undefined behaviour is invoked, possibly in the
35 form of a segmentation fault; they are thus
36 sligtly faster than {\tt zodd} and {\tt zeven}.
37
38 It is discouraged to test the returned value
39 against 1, we should always test against 0,
40 treating all non-zero value as equivalent to 1.
41 For clarity, we use also avoid testing that
42 the returned value is zero, for example, rather
43 than {\tt !zeven(a)} we write {\tt zodd(a)}.
44
45
46 \newpage
47 \section{Signum}
48 \label{sec:Signum}
49
50 There are two functions available for testing
51 the sign of an integer, one of the can be used
52 to retrieve the sign:
53
54 \begin{alltt}
55 int zsignum(z_t a);
56 int zzero(z_t a);
57 \end{alltt}
58
59 \noindent
60 {\tt zsignum} returns $-1$ if $a < 0$,
61 $0$ if $a = 0$, and $+1$ if $a > 0$, that is,
62
63 \vspace{1em}
64 \( \displaystyle{
65 \mbox{sgn}~a = \left \lbrace \begin{array}{rl}
66 -1 & \textrm{if}~ a < 0 \\
67 0 & \textrm{if}~ a = 0 \\
68 +1 & \textrm{if}~ a > 0
69 \end{array} \right .
70 }\)
71 \vspace{1em}
72
73 \noindent
74 It is discouraged to compare the returned value
75 against $-1$ and $+1$; always compare against 0,
76 for example:
77
78 \begin{alltt}
79 if (zsignum(a) > 0) "positive";
80 if (zsignum(a) >= 0) "non-negative";
81 if (zsignum(a) == 0) "zero";
82 if (!zsignum(a)) "zero";
83 if (zsignum(a) <= 0) "non-positive";
84 if (zsignum(a) < 0) "negative";
85 if (zsignum(a)) "non-zero";
86 \end{alltt}
87
88 \noindent
89 However, when we are doing arithmetic with the
90 signum, we may relay on the result never being
91 any other value than $-1$, $0$, and $+0$.
92 For example:
93
94 \begin{alltt}
95 zset(sgn, zsignum(a));
96 zadd(b, sgn);
97 \end{alltt}
98
99 {\tt zzero} returns 0 if $a = 0$ or 1 if
100 $a \neq 0$. Like with {\tt zsignum}, avoid
101 testing the returned value against 1, rather
102 test that the returned value is not 0. When
103 however we are doing arithmetic with the
104 result, we may relay on the result never
105 being any other value than 0 or 1.
106
107
108 \newpage
109 \section{Greatest common divisor}
110 \label{sec:Greatest common divisor}
111
112 There is no single agreed upon definition
113 for the greatest common divisor of two
114 integer, that cover non-positive integers.
115 In libzahl we define it as
116
117 \vspace{1em}
118 \( \displaystyle{
119 \gcd(a, b) = \left \lbrace \begin{array}{rl}
120 -k & \textrm{if}~ a < 0, b < 0 \\
121 b & \textrm{if}~ a = 0 \\
122 a & \textrm{if}~ b = 0 \\
123 k & \textrm{otherwise}
124 \end{array} \right .
125 }\),
126 \vspace{1em}
127
128 \noindent
129 where $k$ is the largest integer that divides
130 both $\lvert a \rvert$ and $\lvert b \rvert$. This
131 definion ensures
132
133 \vspace{1em}
134 \( \displaystyle{
135 \frac{a}{\gcd(a, b)} \left \lbrace \begin{array}{rl}
136 > 0 & \textrm{if}~ a < 0, b < 0 \\
137 < 0 & \textrm{if}~ a < 0, b > 0 \\
138 = 1 & \textrm{if}~ b = 0, a \neq 0 \\
139 = 0 & \textrm{if}~ a = 0, b \neq 0 \\
140 \in \textbf{N} & \textrm{otherwise if}~ a \neq 0, b \neq 0
141 \end{array} \right .
142 }\),
143 \vspace{1em}
144
145 \noindent
146 and analogously for $\frac{b}{\gcd(a,\,b)}$. Note however,
147 the convension $\gcd(0, 0) = 0$ is adhered. Therefore,
148 before dividing with $\gcd(a, b)$ you may want to check
149 whether $\gcd(a, b) = 0$. $\gcd(a, b)$ is calculated
150 with {\tt zgcd(a, b)}.
151
152 {\tt zgcd} calculates the greatest common divisor using
153 the Binary GCD algorithm.
154
155 \vspace{1em}
156 \hspace{-2.8ex}
157 \begin{minipage}{\linewidth}
158 \begin{algorithmic}
159 \RETURN $a + b$ {\bf if} $ab = 0$
160 \RETURN $-\gcd(\lvert a \rvert, \lvert b \rvert)$ {\bf if} $a < 0$ \AND $b < 0$
161 \STATE $s \gets \max s : 2^s \vert a, b$
162 \STATE $u, v \gets \lvert a \rvert \div 2^s, \lvert b \rvert \div 2^s$
163 \WHILE{$u \neq v$}
164 \STATE $v \leftrightarrow u$ {\bf if} $v < u$
165 \STATE $v \gets v - u$
166 \STATE $v \gets v \div 2^x$, where $x = \max x : 2^x \vert v$
167 \ENDWHILE
168 \RETURN $u \cdot 2^s$
169 \end{algorithmic}
170 \end{minipage}
171 \vspace{1em}
172
173 \noindent
174 $\max x : 2^x \vert z$ is returned by {\tt zlsb(z)}
175 \psecref{sec:Boundary}.
176
177
178 \newpage
179 \section{Primality test}
180 \label{sec:Primality test}
181
182 The primality of an integer can be tested with
183
184 \begin{alltt}
185 enum zprimality zptest(z_t w, z_t a, int t);
186 \end{alltt}
187
188 \noindent
189 {\tt zptest} uses Miller–Rabin primality test,
190 with {\tt t} runs of its witness loop, to
191 determine whether {\tt a} is prime. {\tt zptest}
192 returns either
193
194 \begin{itemize}
195 \item {\tt PRIME} = 2:
196 {\tt a} is prime. This is only returned for
197 known prime numbers: 2 and 3.
198
199 \item {\tt PROBABLY\_PRIME} = 1:
200 {\tt a} is probably a prime. The certainty
201 will be $1 - 4^{-t}$.
202
203 \item {\tt NONPRIME} = 0:
204 {\tt a} is either composite, non-positive, or 1.
205 It is certain that {\tt a} is not prime.
206 \end{itemize}
207
208 If and only if {\tt NONPRIME} is returned, a
209 value will be assigned to {\tt w} — unless
210 {\tt w} is {\tt NULL}. This will be the witness
211 of {\tt a}'s completeness. If $a \le 1$, it
212 is not really composite, and the value of
213 {\tt a} is copied into {\tt w}.
214
215 $\gcd(w, a)$ can be used to extract a factor
216 of $a$. This factor is however not necessarily,
217 and unlikely so, prime, but can be composite,
218 or even 1. In the latter case this becomes
219 utterly useless. Therefore using this method
220 for prime factorisation is a bad idea.
221
222 Below is pseudocode for the Miller–Rabin primality
223 test with witness return.
224
225 \vspace{1em}
226 \hspace{-2.8ex}
227 \begin{minipage}{\linewidth}
228 \begin{algorithmic}
229 \RETURN NONPRIME ($w \gets a$) {\bf if} {$a \le 1$}
230 \RETURN PRIME {\bf if} {$a \le 3$}
231 \RETURN NONPRIME ($w \gets 2$) {\bf if} {$2 \vert a$}
232 \STATE $r \gets \max r : 2^r \vert (a - 1)$
233 \STATE $d \gets (a - 1) \div 2^r$
234 \STATE {\bf repeat} $t$ {\bf times}
235
236 \hspace{2ex}
237 \begin{minipage}{\linewidth}
238 \STATE $k \xleftarrow{\$} \textbf{Z}_{a - 2} \setminus \textbf{Z}_{2}$ \textcolor{c}{\{Uniformly random assignment.\}}
239 \STATE $x \gets k^d \mod a$
240 \STATE {\bf continue} {\bf if} $x = 1$ \OR $x = a - 1$
241 \STATE {\bf repeat} $r$ {\bf times or until} $x = 1$ \OR $x = a - 1$
242
243 \hspace{2ex}
244 \begin{minipage}{\linewidth}
245 \vspace{-1ex}
246 \STATE $x \gets x^2 \mod a$
247 \end{minipage}
248 \vspace{-1.5em}
249 \STATE {\bf end repeat}
250 \STATE {\bf if} $x = 1$ {\bf return} NONPRIME ($w \gets k$)
251 \end{minipage}
252 \vspace{-0.8ex}
253 \STATE {\bf end repeat}
254 \RETURN PROBABLY PRIME
255 \end{algorithmic}
256 \end{minipage}
257 \vspace{1em}
258
259 \noindent
260 $\max x : 2^x \vert z$ is returned by {\tt zlsb(z)}
261 \psecref{sec:Boundary}.