\documentclass[11pt]{amsart}
\usepackage[english]{kbexo}
\course{N1MA9W05 -- Master CSI}
\def\kbd#1{\texttt{#1}}
\def\pow{\^{}\hskip0pt}
\def\w{\omega}
\def\FT{\mathcal{F}}
\def\Fp{f_{\text{even}}}
\def\Fi{f_{\text{odd}}}

\begin{document}
\pbtitle{Partial Exam, October 19th 2015 (2pm -- 4pm)}

\smallskip
\centerline{\bf  Duration 2 hours. All documents allowed.}
\bigskip

\noindent Clarity of programs and comments is a major factor in the rating
scale.
\begin{itemize}
\item To answer the questions, create \emph{a single} file per exercise,
  named \kbd{\emph{login}1.gp}, then \kbd{\emph{login}2.gp}, etc. (Type
  \kbd{whoami} in a terminal if you are unsure about your login.) For
  instance, \kbd{kbelabas1.gp}.

\item To hand over your answers, type \url{~kbelabas/copy} in a terminal,
  from the directory where your files are saved.
  (You may do this multiple times, only the last one matters: copies made
  previously are replaced.)
\end{itemize}
\medskip

\exo Find a primality certificate for the integer $300 \times 2^{2015} + 1$.

\exo
\Q Eratosthenes's basic sieve computes primes $\leq B$ via an array
$T$ of length $B$ such that $T[i] = 1$ if and only if $i$ is prime. For
all consecutive primes $p$ the sieve sets $T[i]$ to $0$ in a loop of
type \kbd{forstep(i = p\pow 2, B, p, T[i] = 0)}. Program such a sieve.

\Q Taking care not to forget the prime $2$, it is useless to
consider even numbers. Write a new program yielding an
array $T$ of length $\approx B/2$ such that $T[i] = 1$ if and only
if $2i+1$ is prime. Note that if $p\geq 3$ is prime, then $p^2$ is odd
and the $i = p^2+p$, $p^2+3p$, $p^2+5p$, etc. are even, hence pointless.
How much can we hope to gain compared to $1)$ ?

\Q Let's go further: fix $\delta$ invertible mod $30 = 2\times 3\times 5$.
\qq Obtain the list of all primes of the form $30i + \delta$, via an
array $T$ (of length $\approx B/30$) such that $T[i] = 1$ if and only if
$30i + \delta$ is prime. How much can we hope to gain ?

\qq Obtain the list of all allowed $\delta\in(\ZM/30\ZM)^*$.

\Q* Can one generalize further and continue to gain?

\begin{center}
\large\bf
Around the Fast Fourier Transform (FFT).
\end{center}
Let $n > 1$ be an integer and let $K$ be a commutative field containing
a primitive $n$-th root of unity $\w$. In other words, $\w$ has order
exactly $n$ in $(K^*, \times)$. We define $\w^0 = 1$.
If $K = \FM_q$ is a finite field, such an $\w$ exists if and only if
$n\mid (q - 1)$.

\exo[Examples]
\Q Prove that the characteristic of $K$ can never divide $n$.
\Q Find such an $\w$ for $q = \kbd{nextprime(10\pow60)}$ and
$n = q - 1$.

\Q Find such an $\w$ of multiplicative order $2^{16}$ in a quadratic
finite field $\FM_{p^2}$, such that $\w\not\in\FM_p$.

\Q Fix $n = 2^{32}$; find a prime $p$ such that $n \mid p-1$, then
an $\w$ of order $n$ in $\FM_p^*$.

\exo[Fourier transform]
\noindent
Let $(a_i\colon  0\leq i < n) \in K^n$; by abuse of notation, we identify
such a vector with the polynomial $f = \sum_{0 \leq i < n} a_i X^i$ in
$K[X]_{<n}$. The Fourier Transform of $(a_i)$ relatively to $\w$ is the
vector
$$\FT((a_i), \w) = \FT(f, \w) := (b_j\colon 0 \leq j < n) \in
K^n,\quad\text{where}\quad b_j = f(\w^j).$$
If $k\in \ZM$, we have $\sum_{0\leq i < n} \w^{ik} = 0$ if $n \nmid k$, and
that sum is $n$ otherwise. It follows that                   
$$\FT((b_j\colon 0\leq j < n), \w^{-1}) = (na_i\colon 0\leq i < n),$$
which yields a simple formula for the inverse transform
$\FT^{-1}(\cdot,\omega) = \frac{1}{n}\FT(\cdot,\omega^{-1})$.

\Q Program a naive algorithm to compute the Fourier transform of
$(a_i)$ using $O(n^2)$ operations in $K$ (additions and multiplications).

\Q Same question for the inverse transform.

\exo[FFT]
\noindent We assume from now on that $n = 2^k$, for some integer $k \geq 1$.
Let $f\in K[X]_{<n}$, whose degree is less than $n$, we define $\Fp$ and $\Fi$
by
$$ f = \sum_{i=0}^{n-1} a_i X^i = \Fp(X^2) + X \cdot \Fi(X^2). $$
Let
\begin{align*}
(u_i\colon 0 \leq i < n/2) &:=  \FT(\Fp, \w^2),\\
(v_i\colon 0 \leq i < n/2) &:=  \FT(\Fi, \w^2).
\end{align*}
By abuse of language, we extend $u_j$ and $v_j$ to $j\in \ZM$ by periodicity
modulo $n/2$. We then have $f(\w^j) = u_j + \w^j v_j$ for all $j\in\ZM$.

\Q Program a recursive algorithm for $\FT(f, \w)$ using the previous
formulae.

\Q If your original program did not do so, write a new version assuming
that the vector of all $\omega^i$, $i < n$, are precomputed.

\Q The FFT algorithm uses $O(n\log n)$ opérations in $K$. For a few
well-chosen fields, determine experimental thresholds where the recursive
algorithm beats the naive one.
\end{document}
