\newpage
%Claude Crepeau Number Theory section
\section{Number Theory}
%=====================%
\subsection{Definitions}
%----------------------%
$$a|b \iff \exists k\in Z \,\left[ b=ak \right]$$
$$a\equiv b \pmod{n} \iff n|(a-b)$$
$$b \bmod n \iff \min \{ a>0 : a\equiv b \pmod{n} \}$$
$$b \mbox{ div } n \iff \frac{b- (b \bmod n)}{n} \iff \floor{b/n}$$
$$g = gcd(a,b)
\iff
g|a, g|b \mbox{ and } \left[ g'|a, g'|b \implies g'|g \right]$$
$$\phi(n) = \#\{ a : 00$ {\bf DO}}
\step{$k \is g \mbox{ div } g'$,}
\step{$(\hat{g},\hat{x},\hat{y})\is (g,x,y) -k (g',x',y')$,}
\step{$(g,x,y)\is (g',x',y')$,}
\step{$(g',x',y')\is (\hat{g},\hat{x},\hat{y})$,}
\step{{\bf ENDWHILE} }
\step{{\bf RETURN} $(g,x,y)$.}
}
\subsection{Prime Fields}
%-----------------------%
Let $p$ be a prime number.
The integers $0,1,2,...,p-1$ with operations $+ \bmod p$ et $\times \bmod p$
constitute a field $\GF{p}$ of $p$ elements.
\begin{itemize}
\item contains an additive neutral element (0)
\item each element $e$ has an additive inverse $-e$
\item contains an multiplicative neutral element (1)
\item each non-zero element $e$ has a multiplicative inverse $e^{-1}$
\item associativity
\item commutativity
\item distributivity
\end{itemize}
\pagebreak
\paragraph{Examples}
%''''''''''''''''''%
$\GF{2}=(\BB,\oplus,\wedge)$.
$\GF{5}=(\{ 0,1,2,3,4 \}, +, \times)$ defined by
\begin{figure}[h]
\begin{center}
\begin{tabular}{|r||c|c|c|c|c|}
\hline
$+$ & 0 & 1 & 2 & 3 & 4\\
\hline\hline
0 & 0 & 1 & 2 & 3 & 4 \\
\hline
1 & 1 & 2 & 3 & 4 & 0 \\
\hline
2 & 2 & 3 & 4 & 0 & 1 \\
\hline
3 & 3 & 4 & 0 & 1 & 2 \\
\hline
4 & 4 & 0 & 1 & 2 & 3 \\
\hline
\end{tabular}~~~~~~
\begin{tabular}{|r||c|c|c|c|c|}
\hline
$\times$ & 0 & 1 & 2 & 3 & 4\\
\hline\hline
0 & 0 & 0 & 0 & 0 & 0\\
\hline
1 & 0 & 1 & 2 & 3 & 4\\
\hline
2 & 0 & 2 & 4 & 1 & 3\\
\hline
3 & 0 & 3 & 1 & 4 & 2\\
\hline
4 & 0 & 4 & 3 & 2 & 1\\
\hline
\end{tabular}
\end{center}
%\caption{op\'erations de $\GF{5}$}
\end{figure}
Other kind of finite fields for numbers $q$ not necessarily prime exist.
This is studied in another section. In general we refer to $\GF{q}$ for
a finite field, but you may think of the special case $\GF{p}$ if
you do not wish to find out about the general field construction.
\subsection{Lagrange's Interpolation}
%-----------------------------------%
A polynomial over $\GF{q}$ is specified by a finite sequence $(a_n,a_{n-1},...,a_1,a_0)$
of elements from $\GF{q}$, with $a_n\neq 0$. The number $n$ is the
degree of the polynomial.
\begin{theorem}[Lagrange's Interpolation]
Let $x_0,x_1,...,x_d$ be dinstinct elements of a field $\GF{q}$ and
$y_0,y_1,...,y_d$ be any elements of $\GF{q}$.
There exists a unique polynomial $p(x)$ over $\GF{q}$ with degree $\leq
d$ such that $p(x_i)=y_i$ for $1\leq i\leq n$.
\end{theorem}
\algo{$Interpolation(x_0,x_1,...,x_d,y_0,y_1,...,y_d)$}{
\label{inter}
\step{
\Return
$
\left(
\begin{array}{cccc}
1 & x_0 & \ldots & x_0^d\\
1 & x_1 & \ldots & x_1^d\\
\vdots & \vdots & \ddots & \vdots\\
1 & x_d & \ldots & x_d^d
\end{array}
\right)^{-1}
\left(
\begin{array}{c}
y_0\\
y_1\\
\vdots\\
y_d
\end{array}
\right)
$
}
}
Of course the matrix inversion is to be performed over $\GF{q}$,
which means all additions, substractions and multiplications are
calculated within the field, and divisions are performed by
multiplying with the multiplicative inverse in the field.
\pagebreak
\subsection{Application: Secret Sharing}
%--------------------------------------%
Suppose Alice wants to distribute a secret $S$ among $n$ people
$P_{1},P_{2},\ldots,P_{n}$ in such a way that any $k$ of them
can recover the secret from their joint information, while
it remains perfectly secret when any $k-1$ or less of them get together.
This is what we call a $[n,k]$-secret sharing scheme.
Let's be a bit more formal. Let $S$ be Alice's secret from the finite
set $\{0,1,2,\ldots,M\}$ and let $p$ be a prime number greater than
$M$ and $n$, the number of share holders. Shamir's construction of a
$[n,k]$-secret sharing scheme is as follows.
\algo{SSSS$(S)$}{
\label{SSSS}
\step{$a_{0} \is S$,}
\step{{\bf FOR} $i:=1$ {\bf TO} $k$ {\bf DO} $a_{i} \is uniform(0..p-1)$}
\step{{\bf FOR} $j:=1$ {\bf TO} $n$ {\bf DO}}
\step{$s_{i} \is a_{k} j^k+ a_{k-1} j^{k-1}+\ldots+a_{1} j+a_{0}
\bmod p$}
\step{{\bf ENDFOR}}
\step{{\bf RETURN} $s_{1},s_{2},\ldots,s_{n}$.}
}
Share $s_{j}$ is given to $P_{j}$ secretly by Alice.
In order to find $S$, $k$ or more people may construct
the matrix from Lagrange's theorem from the distinct
values $x_{j}=j$ and find the unique $(a_{0},a_{1},\ldots,a_{k})$
corresponding to their values $y_{j}=s_{j}$.
\begin{theorem}
For $0\leq m \leq n$, distincts $j_{1},j_{2},\ldots,j_{m}$ and any
$s_{j_{1}},s_{j_{2}},\ldots,s_{j_{m}}$
$$\entr{S|[j_{1},s_{j_{1}}],[j_{2},s_{j_{2}}],\ldots,[j_{m},s_{j_{m}}]}
=
\left\{
\begin{array}{ll}
0 & \mbox{if $m \geq k$}\\
\entr{S} & \mbox{if $m < k$}
\end{array}
\right.$$
\end{theorem}
\pagebreak
\subsection{Fast modular exponentiation}
%--------------------------------------%
The idea behind this algorithm is to maintain in each iteration
the value of the expression $x a^e \bmod n$ while reducing
the exponent $e$ by a factor 2.
\algo{$a^e \bmod n$}{
\label{expmod}
\step{$x \is 1$,}
\step{{\bf WHILE} $e>0$ {\bf DO}}
\step{{\bf IF} $e$ is odd {\bf THEN} $x\is ax \bmod n$,}
\step{$a\is a^2 \bmod n$, $e\is e \mbox{ div } 2$,}
\step{{\bf ENDWHILE}}
\step{{\bf RETURN} $x$.}
}
\subsection{Fermat-Euler}
%-----------------------%
\begin{theorem}[Fermat]
\label{Fermat}
Let $p$ be a prime number and $a$ be an integer not a multiple of $p$,
then $$a^{p-1} \equiv 1 \pmod p.$$
\end{theorem}
\begin{theorem}[Euler]
Let $n$ be an integer and $a$ another integer such that $gcd(a,n)=1$,
then $$a^{\phi(n)} \equiv 1 \pmod n.$$
\end{theorem}
\subsection{Prime numbers}
%------------------------%
To decide whether a number $n$ is prime or not
we rely on Miller-Rabin's probabilistic algorithm.
This algorithm relies on the notion of ``pseudo-primality'' base $a$.
\algo{$pseudo(a,n)$}{
\label{pseudo}
\step{{\bf IF} $gcd(a,n)\neq 1$ {\bf THEN RETURN} ``composite'',}
\step{Let $t$ be an odd number and $s$ a positive integer such that $n-1=t 2^s$}
\step{$x\is a^t \bmod n$, $y\is n-1$,}
\step{{\bf FOR } $i \is 1$ {\bf TO } $s$}
\step{{\bf IF} $x=1$ {\bf AND} $y= n-1$ {\bf THEN RETURN}
``pseudo'',}
\step{$y \is x$, $x\is x^2 \bmod n$,}
\step{{\bf ENDFOR} }
\step{{\bf RETURN} ``composite''.}
}
Rabin showed that if $n$ is prime, then $pseudo(a,n)$ returns ``pseudo''
for all $a$, $0 \Else \> \If $a$ is odd \= \Then \= \If $a \equiv n \equiv 3 \pmod 4$\\
\> \> \> \> \Then \= \Return $-Jacobi(n \bmod a,a)$\\
\> \> \> \> \Else \> \Return $+Jacobi(n \bmod a,a)$\\
\> \> \> \Else \> \If $n \equiv \pm 1 \pmod 8$\\
\> \> \> \> \Then \> \Return $+Jacobi(a/2,n)$\\
\> \> \> \> \Else \> \Return $-Jacobi(a/2,n)$
\end{tabbing}
}
}
This algorithm runs in $O((lg \; n)^2)$ bit operations.
\begin{definition}
$$J_n := \{a \in \bbZ_n \; | \; \jacobi{a}{n} = 1 \}$$
\end{definition}
\begin{theorem}
\label{thmProductQR}
Let $n$ be a product of two distinct odd primes $p$ and $q$. Then for an $a \in J_n$
we have that $a \in QR_n$ iff $\jacobi{a}{p} = 1$.
\end{theorem}
\subsection{Quadratic Residuosity problem}
\begin{definition}
The {\it quadratic residuosity problem} (QRP) is the following: given an odd
composite integer $n$ and $a \in J_n$, decide whether or not $a$ is a quadratic
residue modulo $n$.
\end{definition}
\begin{definition}(pseudosquare)
Let $n \geq 3$ be an odd integer. An integer $a$ is said to be a {\it pseudosquare modulo n} if
$\jacobi{a}{n} = 1$ and $a \in QNR_n$.
\end{definition}
\hspace{-0.6cm}{\bf Remark: } If n is a prime, then it is easy to decide if $a$ is
in $QR_n$, since $a \in QR_n$ iff $a \in J_n$, and the Legendre symbol
can be efficiently computed by algorithm \ref{jacobi}.\\
If $n$ is a product of two distinct odd primes $p$ and $q$, then it follows from
theorem \ref{thmProductQR} that if $a \in J_n$, then $a \in QR_n$ iff
$\jacobi{a}{p} = 1$.
If we can factor $n$, then we can found out if $a \in QR_n$ by computing the
Legender symbol $\jacobi{a}{p}$.\\
If the factorization of $n$ is unknown, then there is no efficient algorithm known
to decide if $a \in QR_n$.
\hspace{-0.6cm} This leads to the following Goldwasser-Micali probabilistic encryption algorithm:
\hspace{-0.6cm} {\bf Init: } $Alice$ starts by selecting two large distinct prime numbers $p$ and $q$.
She then
computes $n = pq$ and selects a pseudosquare $y$. $n$ and $y$ will be public, $p$ and $q$ private.
\algo{Goldwasser-Micali probabilistic encryption}{
\step{ Represent message $m$ in binary ($m = m_1m_2 \ldots m_t$).}
\step{ {\bf FOR} $i = 1$ {\bf TO} $t$ {\bf DO}}
\step{ \hspace{0.6cm} {\bf Pick} $x \in_R {\bbZ_n}^*$}
\step{ \hspace{0.6cm} {\bf IF} $m_i = 1$ {\bf THEN} $c_i \leftarrow y x^2 \; mod \; n$}
\step{ \hspace{0.6cm} {\bf ELSE} $c_i \leftarrow x^2 \; mod \; n$}
\step{ {\bf RETURN} $c = c_1c_2 \ldots c_t$}
}
\algo{Goldwasser-Micali decryption}{
\step{ {\bf FOR} $i = 1$ {\bf TO} $m$ {\bf DO}}
\step{ \hspace{0.6cm} $e_i \leftarrow \jacobi{c_i}{p}$ using algo \ref{jacobi}.}
\step{ \hspace{0.6cm} {\bf IF} $e_i = 1$ {\bf THEN} $m_i \leftarrow 0$}
\step{ \hspace{0.6cm} {\bf ELSE} $m_i \leftarrow 1$}
\step{ {\bf RETURN} $m = m_1m_2 \ldots m_t$}
}
\subsection{Extracting Square Roots modulo $n$}
%---------------------------------------------%
\label{SQUARE}
\begin{theorem}
For prime numbers $p\equiv 3 \pmod 4$ and $a\in QR_p$,
we have that $r = a^{(p+1)/4} \bmod p$ is a square root of $a$.
\end{theorem}
\begin{proof}
\begin{eqnarray*}
(a^{(p+1)/4)})^2 &= & a^{(p+1)/2} \\
&= & a^{(p-1)/2}\cdot a \; mod \; p \\
&= & a \; mod \; p \; \; (Fermat, \; sec. \ref{Fermat})
\end{eqnarray*}
\end{proof}
For prime numbers $p\equiv 1 \pmod 4$ and
$a\in QR_p$, there (only) exists an efficient {\it probabilistic}
algorithm.
We present one found in the algorithmics book of Brassard-Bratley
(\cite{BB88}):
\algo{rootLV(x, p, VAR y, VAR success)}{
\step{ $a \leftarrow uniform(1 \ldots p-1)$}
\step{ {\bf IF} $a^2 \equiv x \; mod \; p$ \{very unlikey\} }
\step{ {\bf THEN} $success \leftarrow true$, $y \leftarrow a$}
\step{ {\bf ELSE} compute $c$ and $d$ such that $0 \leq c \leq p - 1, 0 \leq d \leq p-1$, \\
$\; \; \;$ and $(a + \sqrt{x})^{(p-1)/2} \equiv c + d\sqrt{x} \; mod \; p$ }
\step{ \hspace{0.6cm} {\bf IF} $d = 0$ {\bf THEN} $success \leftarrow false$}
\step{ \hspace{0.6cm} {\bf ELSE} $c = 0$, $success \leftarrow true$,}
\step{ \hspace{1.7cm} compute $y$ such that $1 \leq y \leq p - 1$ and $d \cdot y \equiv 1 mod p$}
}
\begin{definition}[SQROOT]
\label{SQROOT}
The square root modulo $n$ problem (SQROOT) can be stated as follows:\\
given a composite integer $n$ and $a \in QR_n$, find a square root
of $a \; mod \; n$.
\end{definition}
\begin{theorem}
SQROOT is polynomialy equivalent to FACTORING (see def. section
\ref{FACTORING}).
\end{theorem}
\subsection{Chinese Remainder Theorem}
%------------------------------------%
\begin{theorem}[Chinese Remainder]
\label{chinese}
Let $m_1,m_2,...,m_r$ be $r$ positive integers such that $gcd(m_{i},m_{j})=1$ for
$1\leq i < j \leq r$ and let $a_1,a_2,...,a_r$ be integers.
The system of $r$ congruences $x \equiv a_{i} \pmod {m_{i}}$, for
$1\leq i\leq r$ has a unique solution modulo $M=m_1 m_2 ... m_r$
which is given by
$$
x = \sum_{i=1}^r a_{i}M_{i}y_{i} \bmod M
$$
where $M_{i}=M/m_{i}$ and $y_{i}=M_{i}^{-1} \bmod \; m_{i}$, for
$1\leq i\leq r$.
\end{theorem}
\hspace{-0.6cm}{\bf Application:}\\
We want to solve $x^2 \equiv a \; mod \; n$ for $x$ knowing $n = pq$.\\
\begin{eqnarray*}
{x_0}^2 &=& a \; mod \; p \\
{x_1}^2 &=& a \; mod \; q
\end{eqnarray*}
We solve \\
\begin{eqnarray*}
x = x_0 \; mod \; p & &\iffimplies p | x^2 - a \\
x = x_1 \; mod \; q & &\underbrace{\iffimplies q | x^2 - a} \\
& &\implies p \cdot q = n | x^2 - a \\
& &\implies x^2 = a \; mod \; n
\end{eqnarray*}
We can now solve $x$ by the chinese remainder theorem.
%End of Claudes Number Theory section.