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