bachelor/book/math_prequisites.tex

\chapter{Mathematical prequisites \label{chap:preq}}

\section{Euclid's Greatest Common Divisor}

Being the gratest common divisor a foundamental algebraic operation in the ssl
protocol, \openssl implemented it with the following signature:

\begin{minted}[fontsize=\small]{c}
  int BN_gcd(BIGNUM *r, BIGNUM *a, BIGNUM *b, BN_CTX *ctx);
\end{minted}

The computation proceeds under the well-known Euclidean algorithm, specifically
the binary variant developed by Josef Stein in 1961 \cite{AOCPv2}. This variant
exploits some interesting properties of $gcd(u, v)$:

\begin{itemize}
  \setlength{\itemsep}{1pt}
  \setlength{\parskip}{0pt}
  \setlength{\parsep}{0pt}
\item if $u,\ v$ are even, then $gcd(u, v) = 2gcd(u/2, v/2)$
\item if $u$ is even and $v$ is odd, then $gcd(u, v) = gcd(u/2, v)$
\item  $gcd(u, v) = gcd(u-v, v)$, as in the standard Euclid's algorithm
\item the sum of two odd numbers is always even
\end{itemize}

% Donald Knuth, TAOCP, "a binary method", p. 388 VOL 2
Both \cite{AOCPv2} and \cite{MITalg} analyze the running time for the algorithm,
even if \cite{clrs}'s demonstration is fairly simpler and proceeds %elegantly
by induction.
Anyway, both show that algorithm ~\ref{alg:gcd} belongs to the class
\bigO{\log b}.

\begin{algorithm}
  \caption{\openssl's GCD \label{alg:gcd}}
  \begin{algorithmic}[1]
    \State $k \gets 0$
    \While{$v \neq 0$}
      \If{$u$ is odd}
        \If{$v$ is odd}
          \State $a \gets (a-b) \ll 1$
        \Else
          \State $b = b \ll 1$
        \EndIf
        \If{$a < b$} $a, b \gets b, a$ \EndIf

      \Else
        \If{$v$ is odd}
          \State $a = a \ll 1$
          \If{$a < b$} $a, b = b, a$ \EndIf
        \Else
          \State $k = k+1$
          \State $a, b = a \ll 1, b \ll 1$
        \EndIf
      \EndIf
    \EndWhile
    \State \Return $a \ll k$

  \end{algorithmic}
\end{algorithm}


\section{RSA Cipher}

XXX.
define RSA, provide the simple keypair generation algorithm.

From now on, except otherwise specified, the variable $N=pq$ will refer to the
public modulis of a generis RSA keypair, with $p, q\ .\ p > q$ being the two primes
factorizing it. Again, $e, d$ will respectively refer to the public exponent and
the private exponent.


\section{Algorithmic Complexity Notation}
The notation used to describe asymptotic complexity follows the $O$-notation,
abused under the conventions and limits of MIT's Introduction to Algorithms.

Let \bigO{g} be the asymptotic upper bound of g:
$$
O(g(n)) = \{ f(n) : \exists n_0, c \in \naturalN \mid 0 \leq f(n) \leq cg(n)
             \ \forall n > n_0 \}
$$

With the writing $f(n) = O(g(n))$ we will actually interpret
$f(n) \in O(g(n))$.

\section{Square Root \label{sec:preq:sqrt}}

Computing the square root has been another foundamental requirement of the
project, though not satisfied by \openssl. Apprently,
% \openssl is a great pile of crap, as phk states
\openssl does not provide
XXX.
define square root in the algebraic notation
discuss method of computation for square root

%%% Local Variables:
%%% mode: latex
%%% TeX-master: "question_authority"
%%% End: