path: root/doc/number-theory.tex

\chapter{Number theory}
\label{chap:Number theory}

In this chapter, you will learn about the
number theoretic functions in libzahl.

\vspace{1cm}
\minitoc


\newpage
\section{Odd or even}
\label{sec:Odd or even}

There are four functions available for testing
the oddness and evenness of an integer:

\begin{alltt}
   int zodd(z_t a);
   int zeven(z_t a);
   int zodd_nonzero(z_t a);
   int zeven_nonzero(z_t a);
\end{alltt}

\noindent
{\tt zodd} returns 1 if {\tt a} contains an
odd value, or 0 if {\tt a} contains an even
number. Conversely, {\tt zeven} returns 1 if
{\tt a} contains an even value, or 0 if {\tt a}
contains an odd number. {\tt zodd\_nonzero} and
{\tt zeven\_nonzero} behave exactly like {\tt zodd}
and {\tt zeven}, respectively, but assumes that
{\tt a} contains a non-zero value, if not
undefined behaviour is invoked, possibly in the
form of a segmentation fault; they are thus
sligtly faster than {\tt zodd} and {\tt zeven}.

It is discouraged to test the returned value
against 1, we should always test against 0,
treating all non-zero value as equivalent to 1.
For clarity, we use also avoid testing that
the returned value is zero, for example, rather
than {\tt !zeven(a)} we write {\tt zodd(a)}.


\newpage
\section{Signum}
\label{sec:Signum}

There are two functions available for testing
the sign of an integer, one of the can be used
to retrieve the sign:

\begin{alltt}
   int zsignum(z_t a);
   int zzero(z_t a);
\end{alltt}

\noindent
{\tt zsignum} returns $-1$ if $a < 0$,
$0$ if $a = 0$, and $+1$ if $a > 0$, that is,

\vspace{1em}
\( \displaystyle{
    \mbox{sgn}~a = \left \lbrace \begin{array}{rl}
        -1 & \textrm{if}~ a < 0 \\
         0 & \textrm{if}~ a = 0 \\
        +1 & \textrm{if}~ a > 0
    \end{array} \right .
}\)
\vspace{1em}

\noindent
It is discouraged to compare the returned value
against $-1$ and $+1$; always compare against 0,
for example:

\begin{alltt}
   if (zsignum(a) >  0)  "positive";
   if (zsignum(a) >= 0)  "non-negative";
   if (zsignum(a) == 0)  "zero";
   if (!zsignum(a))      "zero";
   if (zsignum(a) <= 0)  "non-positive";
   if (zsignum(a) <  0)  "negative";
   if (zsignum(a))       "non-zero";
\end{alltt}

\noindent
However, when we are doing arithmetic with the
signum, we may relay on the result never being
any other value than $-1$, $0$, and $+0$.
For example:

\begin{alltt}
   zset(sgn, zsignum(a));
   zadd(b, sgn);
\end{alltt}

{\tt zzero} returns 0 if $a = 0$ or 1 if
$a \neq 0$. Like with {\tt zsignum}, avoid
testing the returned value against 1, rather
test that the returned value is not 0. When
however we are doing arithmetic with the
result, we may relay on the result never
being any other value than 0 or 1.


\newpage
\section{Greatest common divisor}
\label{sec:Greatest common divisor}

There is no single agreed upon definition
for the greatest common divisor of two
integer, that cover non-positive integers.
In libzahl we define it as

\vspace{1em}
\( \displaystyle{
    \gcd(a, b) = \left \lbrace \begin{array}{rl}
        -k & \textrm{if}~ a < 0, b < 0 \\
        b  & \textrm{if}~ a = 0 \\
        a  & \textrm{if}~ b = 0 \\
        k  & \textrm{otherwise}
    \end{array} \right .
}\),
\vspace{1em}

\noindent
where $k$ is the largest integer that divides
both $\lvert a \rvert$ and $\lvert b \rvert$. This
definion ensures

\vspace{1em}
\( \displaystyle{
    \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 \\
        = 0 & \textrm{if}~ a = 0, b \neq 0 \\
        \in \textbf{N} & \textrm{otherwise if}~ a \neq 0, b \neq 0
    \end{array} \right .
}\),
\vspace{1em}

\noindent
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
with {\tt zgcd(a, b)}.

{\tt zgcd} calculates the greatest common divisor using
the Binary GCD algorithm.

\vspace{1em}
\hspace{-2.8ex}
\begin{minipage}{\linewidth}
\begin{algorithmic}
    \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$}
        \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
    \RETURN $u \cdot 2^s$
\end{algorithmic}
\end{minipage}
\vspace{1em}

\noindent
$\max x : 2^x \vert z$ is returned by {\tt zlsb(z)}
\psecref{sec:Boundary}.


\newpage
\section{Primality test}
\label{sec:Primality test}

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