\documentclass[a4paper,11pt]{article}
\textwidth 15.5cm
\oddsidemargin=0mm
\topmargin=-7mm
\textheight 23 cm
%\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{stmaryrd}
\usepackage{makeidx}
\usepackage{times}
\usepackage{mathptmx}
%Uncomment next line for pdflatex and use includegraphics with eps file
% for latex2html don't use the option [width=\textwidth]
% check that xfig files are exported magnif 100%
 \usepackage{graphicx}
\usepackage{ifpdf}
\ifpdf
 \usepackage[pdftex]{hyperref}
\else
 \usepackage[ps2pdf,breaklinks=true,colorlinks=true,linkcolor=red,citecolor=green]{hyperref}
\fi


%\def\@evenhead{\thepage\hfill{\footnotesize\textit{\leftmark}}}
%\def\@oddhead{\footnotesize{\textit{\rightmark}}\hfill\thepage}
%\usepackage{hp}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[francais]{babel}
\usepackage{latexsym}

\newcommand{\R}{{\mathbb{R}}}
\newcommand{\C}{{\mathbb{C}}}
\newcommand{\Z}{{\mathbb{Z}}}
\newcommand{\N}{{\mathbb{N}}}
\newcommand{\F}{{\mathbb{F}}}

\title{Probl\`eme d'Alg\`ebre de l'Agr\'egation 2007 et \\
traduction pour {\tt Xcas}}
\makeindex
\author{Ren\'ee De Graeve\\Bernard Parisse}

\begin{document}
\maketitle
Les 4 premi\`eres parties sont largement ind\'ependantes
\section{Partie I}
{\em Soit $G$ un groupe multiplicatif de cardinal fini $N \in \mathbb N^*$.}
\begin{enumerate}
\item {\em Justifier le fait que $a^{N-1}$ est l'inverse de $a$ dans $G$.}\\
Si $a=1$ c'est \'evident.\\
Soit $a\neq 1$.\\
Les $N+1$ \'el\'ements $1,a,a^2...a^{N-1},a^N$ sont dans $G$, donc il existe
$p$ et $q$ v\'erifiant $0\leq p<q\leq N$ tel que $a^p=a^q$ c'est \`a dire,
 il existe $0<h=q-p\leq N$ tel que $a^h=1$.\\
Le sous groupe engendr\'e par $a$ est donc d'ordre $h$. On sait que l'ordre 
d'un sous groupe divise l'ordre d'un groupe donc $h$ divise $N$ c'est \`a dire
$N=k*h$ avec  $k \in \mathbb N^*$ donc $a^N=(a^h)^k=1$.
On montre ainsi que $a^{N-1}$ est l'inverse de $a$ dans $G$.

\item {\em On \'ecrit la d\'ecomposition de $N-1$ en base 2 sous la forme~:
\[ N-1=\sum_{i=0}^k x_i2^i, \quad k \in \mathbb N, x_i \in \{0,1\}
\mbox{ pour }
i \in [0,k], x_k \neq 0.
\]
On consid\`ere les suites finies $(a_i)_{0\leq i\leq k+1}$ et
$(b_i)_{0\leq i\leq k+1}$ d\'efinies par~:
\begin{center}
$a_0=1$, $b_0=a$, \quad
pour $i \in [0,k]$, $\ a_{i+1}=a_ib_i^{x_i}$, $\ b_{i+1}=b_i^2$.
\end{center}
}
\begin{enumerate}
\item {\em D\'emontrer que $a_{k+1}$ est l'inverse de $a$ dans $G$.}\\
On a :
\begin{eqnarray*}
a_{k+1} &=&a_k{b_k}^{x_k}\\
a_k&=&a_{k-1}{b_{k-1}}^{x_{k-1}}\\
....\\
a_2&=&a_1b_1^{x_1}\\
a_1&=&a_0b_0^{x_0}
\end{eqnarray*}
Donc puisque $\ a_0=1$, $\ b_0=a$ et $\ b_{i+1}=b_i^2$ on a :
\[ a_1=a^{x_0}  \mbox{ et } b_1=a^2, \quad
a_2=a^{x_0}b_1^{x_1}=a^{x_0}(a^2)^{x_1}=a^{x_0+2x_1} \mbox{ et }
b_2=a^4=a^{(2^2)} \]
Supposons  $a_p=a^{x_0+2x_1+...2^{p-1}x_{p-1}}$ et $b_p=a^{(2^p)}$,
alors~:
\[ a_{p+1}=a_p{b_p}^{x_p}=a^{x_0+2x_1+...2^{p-1}x_{p-1}}{a^{(2^p)}}^{x_p}=
a^{x_0+2x_1+...2^px_p} \]
On a donc montr\'e par r\'ecurrence que :
\[ a_{k+1}=a^{x_0+2x_1+...2^kx_k}=a^{N-1} \]

\item {\em En d\'eduire un algorithme de calcul de $a^{-1}$ et
    pr\'eciser son co\^ut dans le pire des cas.}\\
On \'ecrit tout d'abord {\tt inversG} une fonction {\tt Xcas} qui traduit 
l'algorithme :
\begin{verbatim}
//calcul l'inverse de a dans un groupe mult de cardinal N
inversG(a,N):={
 local b,x,N1;
 N1:=N-1;
 b:=a;
 a:=1;
 while (N1!=0) {
  x:=irem(N1,2);
  N1:=iquo(N1,2);
  a:=a*b^x;
  b:=b^2;
 }
 return a;
}
\end{verbatim}
Dans ce programme, le probl\`eme est que l'on utilise une fonction puissance 
lorsque l'exposant est 0,1 ou 2. Il est donc pr\'ef\'erable de ne faire que des
multiplications et d'\'ecrire {\tt inverseG} :
\begin{verbatim}
//calcul l'inverse de a dans un groupe mult de cardinal N
inverseG(a,N):={
 local b,N1;
 N1:=N-1;
 b:=a;
 a:=1;
 while (N1!=0) {
  if (irem(N1,2)) a:=a*b;
  b:=b*b;
  N1:=iquo(N1,2);
 }
 return a;
}
\end{verbatim}
{\tt inverseG(a,n)} est en fait le calcul dans un groupe $G$ multiplicatif
de $a^{n-1}$. On peut \'ecrire plus g\'en\'eralement,
lorsque $G$ est le groupe des \'el\'ements inversibles de 
$\mathbb{Z}/p\mathbb {Z}$ ayant $n=\mbox{euler}(p)$ \'el\'ements, la fonction 
{\tt puissmod(a,k,p)} qui calcule $a^k \bmod p$ (c'est la fonction interne
{\tt powmod} de {\tt Xcas})~:
\begin{verbatim}
puissmod(a,k,p):={
 local b;
 b:=a;
 a:=1;
 k:=irem(k,euler(p));
 while (k!=0) {
  if (irem(k,2)) a:=irem(a*b,p);
  b:=irem(b*b,p);
  k:=iquo(k,2);
 }
 return a;
}
\end{verbatim}
Si on ne tient pas compte du calcul de {\tt irem(N,2)} et de {\tt iquo(N,2)} 
et, si on fait $k$ fois la boucle, on fait 
$2*k$ multiplications dans le pire des cas lorsque $N-1=2^{k+1}-1$ i.e. lorsque
$k=\log_2(N)-1$, donc
\begin{center}
{\bf On fait $2*\log_2(N)-2$ multiplications.}
\end{center}
Pour ne pas avoir dans la suite du probl\`eme \`a r\'e\'ecrire une fonction
{\tt puissance} pour chaque groupe $G$,
on va \'ecrire une fonction {\tt puissrapide} qui calcule $a^k$ 
avec comme param\`etres un \'el\'ement $a$ du groupe $G$,
$k$ un entier, {\tt mult} le nom de
la loi multiplicative utilis\'ee dans $G$, 
{\tt unit} l'unit\'e de $G$, et {\tt ordre} le cardinal de $G$
s'il est connu ou 0 s'il ne l'est pas (en effet dans {\tt Xcas},
{\tt irem(n,0)=n}).
\begin{verbatim}
puissrapide(a,k,mult,unit,ordre):={
 local b;
 b:=a;
 a:=unit;
 k:=irem(k,ordre);
 while (k!=0) {
  if (irem(k,2)) a:=mult(a,b);
  b:=mult(b,b);
  k:=iquo(k,2);
 }
 return a;
}
\end{verbatim}
Ainsi, pour chaque valeur de $p$, par exemple $p=71$, on d\'efinit la loi 
de multiplication dans $\mathbb{Z}/p\mathbb{Z}$ :
\begin{center}
{\tt multmod71(a,b):=irem(a*b,71);}
\end{center}
On tape pour calculer, par exemple, $47^{750}$ dans 
$\mathbb{Z}/71\\mathbb{Z}$~:
\begin{center}
{\tt puissrapide(47,750,multmod71,1,0)}
\end{center}
Ou on tape puisque l'ordre du groupe multiplicatif de 
$\mathbb{Z}/71\\mathbb{Z}$ est 70~:
\begin{center}
{\tt puissrapide(47,750,multmod71,1,70)}
\end{center}
Ou on tape~:
\begin{center}
{\tt puismod(47,750,71)}
\end{center}
ou encore avec la fonction interne de {\tt Xcas}~:
\begin{center}{\tt powmod(47,760,71)}\end{center}
On obtient :
\begin{center}
{\tt 32}
\end{center}
On tape pour calculer, par exemple, $5^{71}$ dans $\mathbb{Z}/148\
\mathbb{Z}$~:
\begin{center}
{\tt multmod148(a,b):=irem(a*b,148);} \\
{\tt puissrapide(5,71,multmod148,1,0)}
\end{center}
Ou on tape :
\begin{center}
{\tt puismod(5,71,148)}
\end{center}
On obtient :
\begin{center}
{\tt 89}
\end{center}
\end{enumerate}

\item {\em Exemple avec $G$ le groupe des \'el\'ements inversibles de 
$\mathbb{Z}/148\ \mathbb{Z}$}
\begin{enumerate}
\item {\em D\'eterminer le cardinal $N$ de $G$.}\\
$a\in G$ est inversible si $a$ est premier avec $148=4*37$.\\
$G$ est donc l'ensemble des \'el\'ements impairs de 1 \`a 147 auxquels on 
enleve 37 et 3*37=111. \\
$N$ vaut donc 74-2=72.\\
On v\'erifie avec la commande {\tt euler} de Xcas ({\tt euler(148)}
renvoie 72).

\item {\em D\'emontrer que 5 est un \'el\'ement de $G$ et d\'eterminer son 
inverse par la m\'ethode de la question I.2.}\\
5 est premier avec 148 donc 5 est inversible.\\
On tape pour calculer $5^{72-1}$~:
\begin{center}
{\tt puissmod(5,71,148)}
\end{center}
Ou on tape :
\begin{center}
{\tt puissrapide(5,71,multmod148,1,72)}
\end{center}
On obtient~:
\begin{center}
{\tt 89}
\end{center}
On v\'erifie~:
\begin{center}
{\tt 89*5=445=4*148+1}
\end{center}

\item {\em Donner une autre m\'ethode pour calculer cet inverse.}\\
Puisque 5 et 148 sont premiers entre eux, on sait, d'apr\`es 
l'identit\'e de B\'ezout, qu'il existe des entiers relatifs $u$ et $v$ tels 
que $5*u+148*v=1$.\\
On tape~:
\begin{center}
{\tt iegcd(5,148)}
\end{center}
On obtient~:
\begin{center}
{\tt [-59,2,1]}
\end{center}
On a donc $-59*5+2*148=1$ et comme $-59+148=89$ on a~:
\[ 89*5-3*148=1 \]
ainsi l'inverse de 5 est 89 dans $\mathbb{Z}/148\ \mathbb{Z}$.
\end{enumerate}

\end{enumerate}

\section{Partie II}
{\em Soient $\pi$ un \'el\'ement d'un groupe multiplicatif $G$, $e$ un entier
relatif et $\alpha=\pi^e$.
On consid\`ere l'application $f_{\alpha}$ de $\Z\times G$ dans $G^2$ d\'efinie 
par $f_{\alpha}(k,\tau)=(\pi^k,\tau \alpha^k)$.}
\begin{enumerate}
\item
\begin{enumerate}
\item {\em Exhiber une fonction $\phi_e$ de $G^2$ dans $G$, ne  d\'ependant que de $e$ et 
v\'erifiant :}
\[ \forall (k,\tau)\in Z\times G \quad \tau=\phi_e o f_{\alpha}(k,\tau) \]
On a~:
\[ (\pi^k,\tau \alpha^k)=(\pi^k,\tau(\pi^e)^k)=(\pi^k,\tau(\pi^k)^e) \]
Pour $(a,b)\in G^2$, on pose~:
\[ \phi_e(a,b)=b*(a^e)^{-1} \]
o\`u $(a^e)^{-1}$ d\'esigne l'inverse de $a^e$ 
dans $G$. On a ainsi :
\[ \phi_e o f_{\alpha}(k,\tau)=\phi_e(\pi^k,\tau(\pi^k)^e)=\tau \]

\item {\em On suppose $G$ et $\pi$ connu de tous.
La personne {\bf A} garde secret $e$ et rend public $\alpha=\pi^e$ et 
$f_{\alpha}$.\\
On cherche une proc\'edure permettant \`a chacun d'envoyer \`a {\bf A} un 
message crypt\'e sous la forme d'\'el\'ements $\tau$ de $G$ telle que la 
connaissance de $e$ suffise \`a retrouver le message initial.\\
Justifier le fait que si {\bf A} recoit la suite 
$(\lambda_n,\mu_n)=f_{\alpha}(k_n,\tau_n)$ avec $(k_n,\tau_n) \in (Z,G)$ alors
{\bf A} peut d\'ecrypter cette suite gr\^ace \`a $\phi_e$.}

Pour coder le message $\tau$ il suffit de connaitre $\alpha$ et 
$\pi$ : on calcule et on envoie $f_{\alpha}(k,\tau)$ pour un $k$ que l'on 
choisit arbitrairement. La personne qui re\c{c}oit le message connait $e$ donc 
connait $\phi_e$. Elle est donc capable de calculer 
$\phi_e o f_{\alpha}(k,\tau)=\tau$ donc de connaitre le message $\tau$.\\
\end{enumerate}

\item
{\em Dans cette question $G$ est le groupe $\mathbb F_{29}^*$ du corps \`a 29 
\'el\'ements et les nombres $\pi=2$ et $\alpha=18$ sont suppos\'es public.\\
Chaque associ\'e sait que les entiers (1,2...26,27,28) modulo 29 repr\'esentent
les caract\`eres (A,B..Z, '~','.') (27 repr\'esente l'espace et 28 repr\'esente
le point de fin de phrase.)}

\begin{enumerate}
\item 
{\em 
Sachant que {\bf A} d\'ecrypte son message en calculant $a^{17} \bmod 29$
lorsque $a\in (1,2...26,27,28)$, conjecturer la valeur de $e$ et la contr\^oler
gr\^ace \`a $\alpha$.}

Pour d\'ecrypter le message, il faut savoir calculer l'inverse de 
$a^e$ dans $\mathbb F_{29}^*$ lorsque $a$ appartient \`a (1,2...26,27,28).\\
$G$ a 28 \'elements  donc $a^{28}=1  \bmod 29$  donc puisque
$a^{28}=a^{17+11}=a^{17}*a^{11}=1  \bmod 29$ on peut penser que $e=11$\\
On v\'erifie, pour cela on calcule $\pi^e=2^{11} \bmod 29$ et on tape :
\begin{center}
{\tt puissmod(2,11,29)}
\end{center}
On obtient :
\begin{center}
{\tt 18}
\end{center}
ce qui donne bien la valeur de $\alpha$.

\item {\em D\'ecrypter le message suivant (on donne la suite des couples 
$(\lambda_u,\mu_i)$) :\\
(16,17),(18,24),(28,22),(17,21),(23,23),(24,8).}

Pour d\'ecrypter un message on \'ecrit les fonctions servant au
d\'ecodage :
\begin{itemize}
\item 
{\tt decod28(p)} qui a un nombre $p$ entre 1 et 28 retourne le caract\`ere 
correspondant.
\item
{\tt decode(a,b)} qui est la fonction $\phi_e$ ou encore $b*a^{17}$ dans 
$\mathbb F_{29}^*$.
\item
{\tt decodel(L)} qui d\'ecode une liste de couples, représentés
par une liste de 2 éléments, autrement dit une matrice à 2 colonnes.
\end{itemize}
\begin{verbatim}
decod28(p):={
 local r;
 r:=irem(p,29);
 if (r==0) return "erreur";
 if (r<27) return char(p+64);
 if (r==27) return char(32);
 return char(46);
}:;

decode(a,b):={
 return irem(b*powmod(a,17,29),29);
}:;

decodel(L):={
 local s,M;
 s:=size(L);
 M:=NULL;
 for (k:=0;k<s;k++) {
  M:= M,decod28(decode(op(L[k])));
 }
 return M;
}:;
\end{verbatim}
Puis on tape :
\begin{center}
{\tt L:=[[16,17],[18,24],[28,22],[17,21],[23,23],[24,8]]}\\
{\tt decodel(L)}
\end{center}
On obtient :
\begin{center}
{\tt ["C","O","G","I","T","O"]}
\end{center}
\end{enumerate}

\end{enumerate}

\section{Partie III}
{\em
Dans cette partie le corps de base est le corps fini $\mathbb F_{16}$ \`a 16
\'el\'ements, unique \`a un isomorphisme pr\`es.
}

\begin{enumerate}
\item
\begin{enumerate}
\item {\em Comment peut-on construire $\mathbb F_{16}$ ?}

Pour construire $\mathbb F_{16}$, on consid\`ere les polyn\^omes \`a 
coefficients dans $\mathbb Z/2\mathbb Z$ modulo un polyn\^ome irreductible \`a 
coefficients dans $\mathbb Z/2\mathbb Z$ de degr\'e 4.
$\mathbb F_{16}$ est donc compos\'e de quadruplets de nombres valant 0 ou 1
et repr\'esentant un polyn\^ome de degr\'e 3 \`a coefficients dans 
$\mathbb Z/2\mathbb Z$. 

On choisit donc un polyn\^ome $P[X]$ de degr\'e 4 et irr\'eductible dans 
$\mathbb Z/2 \mathbb Z$ et on identifie $\mathbb F_{16}$ \`a 
$(\mathbb Z/2 \mathbb Z)[X]/P[X]$

Avec {\tt Xcas}, on tape :
\begin{center}
{\tt F16:=GF(2,4,['t','F16'])}
\end{center}
ce qui définit le corps {\tt F16}, la variable $t$ sert à représenter
les polynômes à coefficients dans $\Z/2\Z$.
On obtient~:
\begin{center}
{\tt GF(2,t\verb|^|4+t\verb|^|3+1,[t,F16],undef)}
\end{center}
ce qui signifie que Xcas utilise comme polynôme irréductible $t^4+t^3+1$
(c'est le même que celui du sujet, sinon il aurait fallu spécifier
le polynôme irréductible choisi lors de la construction du corps par
l'instruction {\tt GF}).
Ainsi {\tt F16(t\verb|^|4)} renvoie {\tt F16(t\verb|^|3+1)},
et {\tt F16(t\verb|^|5)} renvoie {\tt F16(t\verb|^|3+t+1)}
obtenus par division euclidienne dans $\Z/2\Z$ de $t^4$ ou $t^5$
par $t^4+t^3+1$

\item 
{\em
D\'emontrer que le groupe multiplicatif $\mathbb F_{16}^*$ est form\'e des
puissances successives d'un \'el\'ement $\omega$ v\'erifiant 
$\omega^4+\omega^3+1=0$.}

On cherche l'ordre du groupe engendré par $\omega=\mathbb F_{16}(t)$
c'est-à-dire des restes de $t^k$ par $t^4+t^3+1$.
Comme on sait que l'ordre du groupe multiplicatif $\mathbb F_{16}^*$
est 15, cet ordre est un diviseur de 15, donc 5 ou 15 (visiblement
ce n'est pas 1 ni 3!). On calcule donc le reste de $t^5$
par $t^4+t^3+1$, ce n'est pas 1 donc $\omega$ est bien d'ordre maximal 15.

Remarques~: 
\begin{itemize}
\item l'instruction {\tt GF} de
Xcas renvoie toujours un polynôme irréductible primitif, 
c'est-à-dire que l'ordre du groupe engendré par $t$ est l'ordre
du groupe multiplicatif.
\item Pour former {\tt F16}, on rajoute \`a ces 15 \`el\'ements,
l'\'el\'ement {\tt F16(0)} qui est le z\'ero de $\mathbb F_{16}$.\\
\end{itemize}

\item {\em D\'emontrer que 
$\omega,\omega^2,\omega^4,\omega^8$ sont les racines du polyn\^ome $X^4+X^3+1$
dans  $\mathbb F_{16}$.}

En caractéristique 2, l'application $\phi(x)=x^2$ vérifie
$\phi(x+y)=\phi(x)+\phi(y)$, donc~:
\[ \phi(P(X))=\phi(X^4+X^3+1)=\phi(X^4)+\phi(X^3)+1=\phi(X)^4+\phi(X)^3+1
= P(\phi(X)) \]
Donc, comme $\omega$ est racine de $P=X^4+X^3+1$,
il en est de même de $\phi(\omega)=\omega^2,\phi(\omega^2)=\omega^4,
\phi(\omega^4)=\omega^8$.

Avec {\tt Xcas} on tape :
\begin{center}
{\tt w:=F16(t)}\\
{\tt P(x):=x\verb|^|4+x\verb|^|3+1}\\
{\tt seq(P(w\verb|^|(2\verb|^|k)),k,0,3)}
\end{center}
On obtient :
\begin{center}
{\tt [F16(0),F16(0),F16(0),F16(0)]}
\end{center}

\item 
{\em D\'emontrer que la famille $(\omega,\omega^2,\omega^4,\omega^8)$ est une
base de $\mathbb F_{16}$ sur  $\mathbb F_2$.}

On a $\omega^4=\omega^3+1$ et comme la somme des racines de $X^4+X^3+1$ vaut 1,
on en d\'eduit que 
$\omega^8=1+\omega+\omega^2+\omega^4=\omega+\omega^2+\omega^3$.
On écrit en ligne les coordonnées de cette famille dans la base
canonique $1,\omega,\omega^2,\omega^3$, on trouve
\[ \left(\begin{array}{cccc}
0 &1 &0 &0 \\
0 & 0 & 1 & 0 \\
1 & 0 & 0 & 1 \\
0 & 1 & 1 & 1
\end{array}\right)
\]
On échange la ligne 3 et la ligne 1, puis on ajoute à la ligne 4 les
lignes 2 et 3 à la ligne 4 pour obtenir une matrice triangulaire.

Avec Xcas, on peut utiliser l'instruction {\tt rref(M\%2)} où {\tt M}
désigne la matrice ci-dessus.

On peut aussi faire un raisonnement un peu plus général~:
la famille a le bon nombre d'éléments, il suffit de montrer que
c'est une famille libre. Soit
\[ a \omega + b \omega^2 + c \omega^4 + d \omega^8 =0 \]
une relation linéaire où $a,b,c,d \in \Z/2$ est non identiquement nul.
On applique à cette relation $\phi$ qui est linéaire sur 
le $\Z/2$-espace vectoriel $\F_{16}$, puis à nouveau $\phi$ et $\phi$.
On obtient un système linéaire de 4 équations où $a,b,c,d$
subissent une rotation, en faisant la somme des 4 équations,
on montre que $a+b+c+d$ est nul. Donc le nombre de 1 est pair.
Il ne peut valoir 4 (la somme des racines est 1), ni 2 (les
racines sont distinctes 2 à 2), donc vaut 0.

\end{enumerate}

\item
\begin{enumerate}
\item {\em Soit $a \in \mathbb F_{16}$. R\'esoudre dans $\mathbb F_{16}$ 
l'\'equation $x^5=a$, en discutant selon les valeurs de $a$.}

On sait que pour tout $x \in \mathbb F_{16}^*$, on a $x^{15}=1$ donc si 
$x^5=a$ admet une solution, alors $a^3=1$ dont les solutions sont
les $\omega^{5k}$ pour $k=0,1,2$. 
Les racines de l'équation $x^5=\omega^{5k}$ sont $\omega^{k+3l}$ pour
$l=0,1,2,3,4$.


\item {\em
D\'emontrer qu'il existe quatre \'el\'ements $\gamma \in \mathbb F_{16}$ 
tels que $\gamma,\gamma^2,\gamma^4,\gamma^8$ est une base de $\mathbb F_{16}$
sur $\mathbb F_2$ telle que le produit de 2 de ses \'el\'ements appartient \`a 
la base ou est \'egal \`a 1.\\
Expliquer rapidement pourquoi les calculs dans $\mathbb F_{16}$ sont plus 
faciles dans une telle base.}

On choisit l'une des 4 solutions diff\'erentes de 1 de $x^5=1$ comme 
valeur de $\gamma$, en effet si $\gamma^5=1$ avec $\gamma \neq 1$ on a
$\gamma^4+\gamma^3+\gamma^2+\gamma+1=0$.
On a alors  :
\begin{eqnarray*}
\gamma \gamma^2 = \gamma^3 &=& \gamma^8 \\
\gamma \gamma^4 = \gamma^5 &=& 1 \\
\gamma \gamma^8 = \gamma^9 &=& \gamma^4\\
\gamma^2 \gamma^4 = \gamma^6 &=& \gamma \\ 
\gamma^2 \gamma^8 = \gamma^{10} &=&1 \\
\gamma^4 \gamma^8 = \gamma^{12}&=&\gamma^2
\end{eqnarray*}
Si $\gamma\neq 1$ est solution de $x^5=1$, $\gamma^2,\gamma^4,\gamma^8$
sont les 3 autres solutions de $x^5=1$ différentes de 1
puisque $(\gamma^n)^5=1$ quelque soit $n$. On peut démontrer 
comme ci-dessus qu'ils forment une famille libre. On peut aussi
faire le calcul, par exemple si $\gamma=\omega^3$ on a :
\[ \gamma=t^3, \quad \gamma^2=t^3+t^2+t+1, \quad
\gamma^4=t+1, \quad \gamma^8=t^2+1\]
sont les solutions de $x^5=1$ diff\'erentes de 1.
On montre facilement que 
$ [t^3,t^3+t^2+t+1,t^2+1,t+1]$ forment une base de $\mathbb F_{16}$ 
puisque ils sont ind\'ependants et au nombre de 4.

La multiplication est plus rapide dans la base 
$\gamma,\gamma^2,\gamma^3=\gamma^8,\gamma^4$ car
\[ 1=\gamma^4+\gamma^3+\gamma^2+\gamma \]
on peut donc faire la multiplication 
avec un algorithme semblable \`a celui utilis\'e avec les entiers \'ecrits en 
base 10.\\
On \'ecrit le programme {\tt multi(a,b)} qui renvoie les coefficients du 
produit $a*b$ dans la base $\gamma,\gamma^2,\gamma^3,\gamma^4$ lorsque $a$ et 
$b$ sont des \'el\'ements de $\mathbb F_{16}$ 
donn\'es par tous leurs coefficients dans cette base :
\begin{verbatim}
multi(a,b):={
 local c,ci,k,j,p,u;
 c:=[];
 for (j:=3;j>=0;j--){
  ci:=[0];
  for (k:=3;k>=0;k--){
   ci:=prepend(ci,(a[k] and b[j]));
  }
  for (p:=0;p<=3-j;p++){
   ci:=append(tail(ci),head(ci));
  }
  u:=ci[4];
  for (p:=0;p<4;p++){
    ci[p]:=ci[p] xor u;
  }
  ci[4]:=0;
  c:=append(c,mid(ci,0,4));
 }
 for (j:=3;j>0;j--){
  for (k:=3;k>=0;k--){
   c[j-1,k]:=c[j,k] xor c[j-1,k];
  }
 }
return c[0];
}
\end{verbatim}
On tape par exemple :
\begin{center}
{\tt multi([1,0,1,1],[0,1,1,1])}
\end{center}
On obtient :
\begin{center}
{\tt [0,0,0,1]}
\end{center}
ce qui veut dire que~:
\[ (\gamma^4+\gamma^2+\gamma)*(\gamma^3+\gamma^2+\gamma)=\gamma \]
On v\'erifie en tapant ({\tt c:=w\verb|^|3} repr\'esente $\gamma$) :
\begin{center}
{\tt c:=w\verb|^|3;}\\
{\tt (c\verb|^|4+c\verb|^|2+c)*(c\verb|^|3+c\verb|^|2+c)}
\end{center}
On obtient :
\begin{center}
{\tt F16(t\verb|^|3)}
\end{center}

{\bf Remarque}~: 
le plus efficace (pour des corps de cardinal petit),
c'est de coder les éléments du corps
par l'exposant de $\omega$ ou par 15 pour $0_{\F_{16}}$
(représentation dite multiplicative). La multiplication est
alors triviale~: si l'un des arguments vaut 15, on renvoie 15, sinon
on renvoie la somme des exposants modulo 15.
Pour l'addition, il faut d'abord passer en représentation
additive, où l'élément du corps est codé sur un entier de 4 bits,
chaque bit représentant une coordonnée dans la base 
$\omega^3,\omega^2,\omega,1$. En effet, en représentation additive,
l'addition se code par un ou exclusif. 
Le passage entre les deux représentations
se fait par l'intermédiaire d'une table calculée une fois pour
toutes (la table se calcule uniquement avec des opérations de décalage et
de ou exclusif avec un entier sur 5 bits représentant le polynôme minimal
de $\omega$, dans notre cas {\tt 0b11001}). 

Par exemple, en repr\'esentation multiplicative, $\omega^5$ et
$\omega^4$ sont repr\'esent\'es respectivement par 5 et 4.
Leur produit est $\omega^9$ repr\'esent\'e par $9=5+4 \pmod 15$.
Pour trouver leur somme, il faut passer en repr\'esentation additive,
dans la base $\omega^3,\omega^2,\omega,1$, l'\'el\'ement 
$\omega^5$ est $(1,0,1,1)$, soit {\tt 0b1011} en base 2, 
l'\'el\'ement $\omega^4$ est $(1,0,0,1)$, soit
{\tt 0b1001} en base 2, donc la somme de $\omega^5$ et $\omega^4$
est {\tt bitxor(0b1011,0b1001) = 0b0010}, c'est donc $\omega$,
repr\'sent\'e par 1 en repr\'esentation multiplicative.

% Si on reprend l'exemple trait\'e ci dessus :\\
% $c^4+c^2+c=\omega^{12}+\omega^6+\omega^3=\mathbb F_{16}(t^2)$ et
% $c^3+c^2+c=\omega^9+\omega^6+\omega^3=\mathbb F_{16}(t)$ donc
% $(c^4+c^2+c)*(c^3+c^2+c)=\mathbb F_{16}(t^3)=c$.\\
Ceci se généralise en caractéristique 2, on utilise d'ailleurs
souvent $\F_{256}$ car l'élément du corps est alors représenté
par un octet.
\end{enumerate}

\end{enumerate}

\section{Partie IV}
{\em Une cubique sur un corps $\mathbb K$ est l'ensemble des points 
$M=(x,y) \in \mathbb K^2$ annulant un polyn\^ome $P$ non nul du 3i\`eme 
degr\'e en $X$ et $Y$ \`a coefficients dans $\mathbb K$.\\
Cette partie \'etudie quelques cubiques particuli\`eres sur $\mathbb R$.
}
\begin{enumerate}
\item Dans cette question, on prend la cubique $\Gamma$ d\'efinie par le 
polyn\^ome :
\[ P=X^3-Y \in \mathbb R[X,Y] \]
\begin{enumerate}
\item {\em La tracer \`a main lev\'ee.}\\
Avec {\tt Xcas}, on tape :
\begin{center}
{\tt plot(x\verb|^|3)}
\end{center}
On obtient le graphe de $\Gamma$ qui est l'ensemble des points 
$M=(x,y) \in \mathbb R^2$ tel que $y=x^3$.\\
\includegraphics[width=\textwidth]{agregx3}\\
On d\'emontre facilement que $x->x^3$ est une bijection de $\mathbb R$ dans 
$\mathbb R$ et que $\Gamma$  admet le point (0,0) comme centre de sym\'etrie.

\item {\em
 D\'emontrer que toute droite coupe $\Gamma$ en exactement 1 ou 3 points en
comptant leur multiplicit\'e \'eventuelle et que lorsqu'il y a 3 points 
d'intersection not\'es $A=(x_A,y_A)$, $B=(x_B,y_B)$, $C=(x_C,y_C)$ on a :
$x_A+x_B+x_C=0$.}

Les points d'intersection de $\Gamma$ avec la 
droite d'\'equation : $ux+vy+w=0$ ont des abscisses qui v\'erifient :
 \[ ux+vx^3+w=0 \]
L'\'equation en $x$, $vx^3+ux+w=0$ est une \'equation du troisi\`eme degr\'e 
\`a coefficients r\'eels. Cette \'equation admet donc soit 1 racine r\'eelle et
2 racines complexes conjugu\'ees, soit 3 racines r\'eelles en
comptant leur multiplicit\'e \'eventuelle. \\
On remarque que le terme en $x^2$ a un coefficient nul donc la somme des 
racines vaut 0 et donc lorsqu'il y a 3 racines, il y  3 points 
d'intersection $A=(x_A,y_A)$, $B=(x_B,y_B)$, $C=(x_C,y_C)$
et on a :$x_A+x_B+x_C=0$.

\item
{\em On note $\Omega$ le point (0,0) de $\Gamma$. Pour tout couple de points 
$(A,B)$ de $\Gamma$, on note $d$ la droite passant par $A$ et $B$ (ou la 
tangente en $A$ si $A=B$) et on consid\`ere le point $C=\Gamma \cap d$. On
d\'efinit $A*B$ comme \'etant le point d'intersection de $\Gamma$ avec la 
droite $\Omega C$ (ou avec la tangente en  $\Omega$ si $\Omega=C$).\\
D\'emontrer que  $(\Gamma,*)$ est un groupe isomorphe \`a  $(\mathbb R,+)$.}
 
La droite $d$ passe par $A$ et par $B$ donc recoupe $\Gamma$ en un troisi\`eme 
point $C$ dont l'abscisse $x_C$ vaut~:
\[ x_C=-(x_A+x_B) \]
Puisque $\Omega$  est un centre de sym\'etrie pour $\Gamma$, la droite 
$\Omega C$ coupe $\Gamma$ au point $D=A*B$ d'abscisse~:
\[ x_{A*B}=x_D=-x_C=(x_A+x_B) \]
% car le graphe de $\Gamma$ est sym\'etrique par 
% rapport \`a $\Omega$ puisque c'est le graphe d'une fonction impaire.\\
Soit $f$ la projection des points de $\Gamma$ sur l'axe des $x$ c'est \`a dire 
l'application de $(\Gamma,*)$ dans $(\mathbb R,+)$ d\'efinie par :
$f(M)=x_M$ pour tout $M \in \Gamma$.

On vérifie que $f$ est bijective, 
en effet soit $a \in \mathbb R$ alors il existe un seul 
point $A$ de $\Gamma$ tel que $f(A)=a$ : c'est le point de coordonn\'ees 
$a,a^3$. De plus~:
\[ f(A*B)=f(D)=x_D=x_A+x_B=f(A)+f(B) \]
Donc $f$ est un isomorphisme du groupe $(\Gamma,*)$ sur $(\mathbb R,+)$
puisque $f$ est bijective et v\'erifie $f(A*B)=f(A)+f(B)$.
\end{enumerate}

\item {\em Reprendre la question 1/ pour $P=X^3-3XY-1 \in \mathbb R[X,Y]$ et 
$\Omega=(0,1)$ en pr\'ecisant \`a quel groupe usuel
est isomorphe $(\Gamma,*)$ dans cet exemple.}

Le graphe de $\Gamma$  de $x^3-3xy-1=0$ admet l'axe des $y$ 
comme asymptote et admet une branche parabolique de direction l'axe des $y$.\\
En effet, si $x\neq 0$ on a 
\[ y=\frac{x^3-1}{3x}=\frac{x^2}{3}-\frac{1}{3x} \] 
donc, lorsque x tend vers 0 alors $y$ tend vers l'infini et
lorsque x tend vers l'infini alors $y$ tend vers l'infini et $y/x$ tend vers 
l'infini.

Avec {\tt Xcas}, on tape :
\begin{center}
{\tt G:=plot((x\verb|^|3-1)/(3x),x=-3..3);}\\
{\tt affichage(point(1,0),point\_width\_3+rouge);}\\
{\tt d:=tangente(G,1);}
\end{center}

Le point (1,0) appartient \`a $\Gamma$ et la tangente en ce point au graphe de 
$\Gamma$ est la droite $y=x-1$.
Toutes les droites sauf l'asymptote $x=0$ coupent le graphe de $\Gamma$ 
en 1 ou 3 points, les verticales $x=a$ coupent $\Gamma$ en 1 seul point 
et les droites $y=ax+b$ coupent $\Gamma$ en un ou trois points 
$M=(x,y)$ d'abscisse vérifiant~:
\[ x^3-3ax^2-3bx-1=0 \]
On remarque que le produit des racines de ce polyn\^ome est indépendant
de $a$ et $b$.
Donc, lorsqu'une droite coupe le graphe de $\Gamma$ en trois points
$A=(x_A,y_A)$, $B=(x_B,y_B)$ et $C=(x_C,y_C)$ on a~:
\[ x_A\times x_B\times x_C=1 \]
Si $C$ est confondu avec $\Omega$, la droite $\Omega C$ est la tangente en 
$\Omega$ d'\'equation $y=x-1$ et $D$ est confondu avec $\Omega$.\\
Cherchons l'intersection de la droite $\Omega C$ avec $\Gamma$ lorsque 
$C \neq \Omega $ i.e. lorsque $x_C \neq 1$.
La droite $\Omega C$ coupe $\Gamma$ en $\Omega,C$ et $D=A*B$.
Les abscisses de ces  points d'intersection v\'erifient :
\[ 1\times x_C\times x_D=1 \]
et on sait que $x_A\times x_B\times x_C=1$, donc 
\[ x_{A*B}=x_D=1/x_C=x_A\times x_B \]
On note toujours $f$ la projection des points de $\Gamma$ sur l'axe des $x$,
c'est une bijection de $\Gamma$ sur $\mathbb R^*$ car pour tout 
$a \in \mathbb R^*$ il existe un seul point $A$ de $\Gamma$ v\'erifiant
$f(A)=a$ : c'est le point de coordonn\'ees $(a,(a^3-1)/(3a))$.
De plus
\[ f(A*B)=x_A\times x_B=f(A)\times f(B)\] 
Donc $f$ est un isomorphisme du groupe $(\Gamma,*)$ sur $(\mathbb R^*,\times)$
puisque $f$ est bijective et v\'erifie $f(A*B)=f(A)\* f(B)$.
Donc  $(\Gamma,*)$ est un groupe isomorphe \`a  $(\mathbb R^*,\times)$.

\item
{\em On \'etudie dans la suite des cubiques du plan projectif.
Au polyn\^ome $P$ de degr\'e 3,  on associe le polyn\^ome homog\'ene~:
\[ \overline{P}(X,Y,Z)=Z^3P(X/Z,Y/Z) \]
$\Gamma$ est alors l'ensemble des points du plan projectif dont les 
coordonn\'ees homog\'enes $(X,Y,Z)$ v\'erifient $\overline{P}(X,Y,Z)=0$.

D\'emontrer que que l'intersection de $\Gamma$  avec toute droite du plan
projectif est constitu\'ee d'exactement 1 ou 3 points en comptant les 
multiplicit\'es \'eventuelles.}

Une droite $d$ du plan projectif a pour \'equation
$uX+vY+wZ=0$ avec $u,v,w$ non tous nuls donc l'une des coordonn\'ees 
s'exprime en fonction des deux autres dite variables principales, donc les 
variables principales des points d'intersection de $d$ et de la cubique 
v\'erifient une \'equation homog\`ene de degr\'e 3 donc cela donne 1 ou 3 
couples de variables principales solutions donc 1 ou 3 points d'intersection.

\item {\em Soit $P=y^3-y^2-x^2$ et $\overline P= Y^3-Y^2Z-X^2Z$.}
\begin{enumerate}
\item {\em 
Soit $\gamma$ la courbe d'\'equation $y^3-y^2-x^2=0$ priv\'ee du point 
(0,0).
En choisissant un param\'etrage de $\gamma$ (par exemple en coordonn\'ees 
polaires) \'etudier cette courbe et la tracer, en pr\'ecisant l'allure des 
branches infinies si il en existe. On ne demande pas les points d'inflexion.
}

Puisque $(0,0)$ est exclu, $y^2+x^2\neq 0$ et $y\neq 0$, en effet
si $y=0$ et si $y^3-(y^2+x^2)=0$ alors $x=0$.

De plus on voit que $\gamma$ est situ\'e dans le demi-plan $y \geq 1$ 
(puisque $y^3 \geq y^2$) et 
$\gamma$ est sym\'etrique par rapport \`a l'axe des $y$.
 
On a en coordonn\'ees polaires $x=r\cos(\theta),y=r\sin(\theta)$ 
pour $\theta \in ]0,\pi[$, donc
\[y^3-(y^2+x^2)=r^3\sin(\theta)^3-r^2=0 \]
Puisque $r \neq 0$, on en d\'eduit un param\'etrage de $\gamma$ 
en coordonn\'ees polaires :
\[ r=1/\sin(\theta)^3, \quad \mbox{ pour } \theta \in ]0,\pi[ \]
On peut aussi trouver un un param\'etrage de $\gamma$ en coordonn\'ees 
param\'etriques en posant pour $t\in \mathbb R$, $x=ty$.  On 
a alors puisque $y \neq 0$~:
\[ y^3-(y^2+x^2)=y^2(y-(1+t^2))=0 \ \Rightarrow \ y=(1+t^2) \] 
Donc un param\'etrage de $\gamma$ en coordonn\'ees param\'etriques est~:
\[ x=t(1+t^2),y=(1+t^2) \mbox{ pour } t\in \mathbb R \]
Pour l'\'etude de la courbe en coordonn\'ees polaires, il suffit de prendre 
$\theta \in ]0,\pi/2]$ et de compl\'eter par la sym\'etrie d'axe
l'axe des $y$.

Pour \'etudier les branches infinies, en coordonn\'ees polaires, $x$ et $y$
tendent vers l'infini quand  $\theta$ vers 0. On a alors
$y/x=\tan(\theta)$ qui tend vers 0 quand  $\theta$ vers 0.
Donc $\gamma$ admet donc une branche parabolique de direction l'axe des $x$.

On a donc deux branches paraboliques de direction l'axe des $x$. Ces deux
branches paraboliques sont sym\'etriques par rapport \`a l'axe des $y$ et
correspondent au trac\'e de la courbe quand $\theta$ tend vers 0 pour 
l'une et au trac\'e de la courbe quand $\theta$ tend vers $\pi$ pour l'autre.

Pour l'\'etude de la courbe en coordonn\'ees param\'etriques, il suffit 
de prendre $t>0$ car $x$ est une fonction impaire en $t$ et $y$ 
est une fonction paire en $t$. La courbe est donc sym\'etrique par 
rapport \`a l'axe des $y$.
Pour \'etudier les branches infinies, en coordonn\'ees param\'etriques, on 
fait tendre $t$ vers plus l'infini alors  $x$ et $y$ tendent vers plus l'infini
et $y/x=1/t$ tend vers 0.
Donc $\gamma$ admet donc deux branches paraboliques sym\'etriques de direction
l'axe des $x$.

Avec {\tt Xcas}, on tape en coordonn\'ees polaires~:
\begin{center}
{\tt plotpolar(1/sin(t)\verb|^|3,t,0,pi)}
\end{center}
Ou en  en coordonn\'ees paramétriques :
\begin{center}
{\tt plotparam((1+t\verb|^|2)*(t+i),t)}
\end{center}

\item {\em
 Dans la suite de la question 4, on consid\`ere dans le plan projectif la 
cubique $\Gamma$ d'\'equation $Y^3-Y^2Z-X^2Z=0$, priv\'ee du point (0,0,1).\\ 
On choisit $\Omega=(1,0,0)$ le point \`a l'infini du plan dans la direction 
de la droite des $x$, et on d\'efinit le compos\'e $A*B$ de deux points de 
$\Gamma$ comme en IV.1.
Montrer que $\Gamma$ admet comme param\'etrage :
\[ X=\cos(\theta), Y=\sin(\theta),Z=\sin(\theta)^3
\mbox{ pour } \theta \in\mathbb R \]
Si $A$ et $B$ sont deux points de  $\Gamma$ caract\'eriser le point $C$
d'intersection de la droite $AB$ avec $\Gamma$, puis le point $D=A*B$.
D\'emontrer que $(\Gamma,*)$ est isomorphe \`a un groupe usuel que l'on 
pr\'ecisera.\\ 
Quels sont les points d'ordre 6 ?}

\includegraphics[width=\textwidth]{agregpol}

On prend les points du plan projectif correspondant aux points
de $\gamma$ paramétrés en coordonnées polaires 
$(r \cos(\theta),r \sin(\theta),1)$, donc ce sont les points
$(\cos(\theta),\sin(\theta),1/r)=(\cos(\theta),\sin(\theta),\sin(\theta)^3)$
Les branches infinies de $\gamma$ correspondent à $\theta=0 \pmod \pi$.

Cherchons l'intersection d'une droite $aX+bY+cZ=0$ avec  $\Gamma$,
cela revient à chercher les $\theta$ tels que
\[ a \cos(\theta) + b \sin(\theta) + c \sin(\theta)^3=0\]
Si $a=0$, alors $\theta=0$ est solution et réciproquement, 
si de plus $c\neq 0$ est de signe opposé à $b$, les 2 autres solutions 
dans $[-\pi/2,\pi/2]$ sont de sinus opposés, donc sont opposées.

Après division par $\sin(\theta)$ pour $\theta \neq 0 \pmod \pi$, 
et en notant $t=1/\tan(\theta)=\cot(\theta)$ on a 
(puisque $1+\cot(\theta)^2=1/\sin(\theta)^2$)~:
\[ a t + b  + c \frac{1}{1+t^2} =0 \]
soit~:
\[ a t^3 + b t^2 + a t + b + c = 0\]
Pour $a\neq 0$, cette équation admet 3 solutions (dont 1 ou 3 réelles), 
qui vérifient
\[ t_1 t_2 + t_1 t_3 + t_2 t_3  = 1 \]
donc~:
\[ t_3 = \frac{1-t_1 t_2}{t_1+t_2}\]
Puisque 
$\displaystyle \cot(\theta_1+\theta_2)=\frac{\cot(\theta_1)\cot(\theta_2)-1}{\cot(\theta_1)+\cot(\theta_2)}$, s'il y a 3 solutions réelles, l'angle $\theta_3$ 
correspondant à $t_3$ vérifie alors $\cot(\theta_3)=-\cot(\theta_1+\theta_2)$ 
donc~:
\[ \theta_3 = - (\theta_1 + \theta_2) \pmod \pi \]
Donc le 3ème point d'intersection $C$ d'une droite coupant la cubique
en 2 points $A$ et $B$
de paramètres $\theta_1$ et $\theta_2$ vérifie dans tous les cas
\[ \theta_3 = - (\theta_1 + \theta_2) \pmod \pi \]
De plus si on trace la droite passant par les points de paramètre $\theta_3$
et $0$, elle coupe à nouveau la cubique au point $D$ de paramètre 
$-\theta_3=\theta_1+\theta_2$.
Finalement la loi de composition de 2 points sur la cubique
revient à additionner les paramètres modulo $\pi$, elle munit
donc la cubique d'une structure de groupe isomorphe à $\R/\pi\Z,+$.

Les points d'ordre 6 correspondent aux angles $\theta$ tels que
$6 \theta = 0 \pmod \pi$, ce sont donc les 6 points d'angles respectifs
$0, \pm \pi/6, \pm \pi/3, \pi/2$.

%% On a aussi $\Gamma$ est compos\'e des points d'affixe :\\
%% $(1+t^2)*(t+i)$ quand $t \in\mathbb R$ et du point $\Omega$ (le point \`a 
%% l'infini du plan dans la direction de la droite des $x$).\\
%% On remarque que :\\
%% les droites passant par l'origine coupent $\Gamma$ en un seul 
%% point, en effet :\\
%% $aX-Y=0$ coupe $\Gamma$ en $(a^2+1,a(a^2+1),a^3)$ (car $a^3X^3=(a^2+1)X^2Z$
%% et $X\neq 0$ puisque $Y\neq 0$),\\
%% $X=0$ coupe $\Gamma$ en $(0,1,1)$ (car $Y^3=Y^2Z$ et $Y\neq 0$)\\
%% $Z=0$ coupe $\Gamma$ en $\Omega=(1,0,0)$ ($\Omega$ est une racine triple car 
%% $Y^3=0$)\\
%% on a soit 
%% $a^3X^3=(a^2+1)X^2Z$, soit $Y^3=Y^2Z$ soit $Y^3=0$\\
%% On remarque ausi que :\\
%% les droites passant par $\Omega=(1,0,0)$ sont les droites 
%% parall\`eles \`a l'axe des $x$ et qu'elles coupent $\Gamma$ en 
%% deux points sym\'etriques par rapport l'axe des $y$.\\
%% Donc :
%% \begin{itemize}
%% \item si $A=B=\Omega=(1,0,0)$, la droite $AB$ coupe
%% $\Gamma$ en $\Omega$ et donc $\Omega*\Omega=\Omega$.
%% \item si $A=\Omega=(1,0,0)$ et si $B\neq \Omega$, alors
%% $A*B=\Omega*B=B*\Omega=B$  
%% \item  si $A=B$ mais $A \neq \Omega$ on pose :\\
%% $A=(x_A,y_A,Z_A=1)$ et $B=(x_B,y_B,Z_B=1$.\\ 
%% La tangente $d$ en $A$ \`a $\Gamma$ a  pour \'equation :\\
%% $(3y_A^2-2y_A)(Y-y_AZ)-2x_A(X-x_AZ)=0$\\
%% Les abscisses des points d'intersection de $d$ et $\Gamma$ v\'erifient :\\
%% $(3y_A^2-2y_A)Y-2x_AX+(2x_A^2+2y_A^2-3y_A^3)Z$ et\\
%% $Y^3-Y^2Z-X^2Z=0$.\\
%% Le coefficient  $k=(2x_A^2+2y_A^2-3y_A^3)=-y_A^3$ de $Z$ n'est pas nul car
%% $A$ est diff\'erent de  $\Omega$ donc puisque (0,0,1) est exclu :\\
%% $-k*Z=-k*Y^3/(X^2+Y^2)=(3y_A^2-2y_A)Y-2x_AX$\\
%% Donc $X$ et $Y$ v\'erifient une \'equation homog\`ene du 3i\`eme degr\'e :\\
%% $(-3y_A^2+2y_A-k)*Y^3=-2x_AXY^2+3y_A^2X^2Y-2x_AX^3$\\
%% dans cette \'equation les coefficients de $X^3$ et de $Y^2X$ sont les m\^emes
%% donc :\\
%% - soit $Y=0$ est solution, on a  $2x_AX^3=0$ et comme
%% (0,0,1) est exclu, cela entraine $x_A=0$ c'est \`a dire $A$ est le point 
%% (0,1,1) de $\Gamma$. Donc le point $C=\Omega$ et le point $D=A$.
%% Donc $(0,1,1)*(0,1,1)=(0,1,1)$.\\
%% - soit  $Y=0$ n'est pas solution, alors on peut poser $X/Y=a$ 
%% et l'\'equation a 3 racines $a_1=a_2=x_A/y_A,a_3$ qui v\'erifient :\\
%% $a_1^2+2a_1a_3=1$.\\ 
%% On a ainsi $a_3=X_C/Y_C=(1-a_1^2)/(2a_1)$ et donc \\
%% $$X_D/Y_D=(a_1^2-1)/(2a_1)$$
%% On pose $f(t)=t(t^2+1)$ et $g(t)=t^2+1$.
%% Si $A$ est un point de $\Gamma$ diff\'erent de $\Omega$, on pose
%% $x_A/y_A=a_1$.\\ 
%% Alors $A$ est le point $f(a_1),g(a_1)$ 
%% et $D=A*A$ et le point $f(a_3),g(a_3)$ avec $a_3=(a_1^2-1)/(2*a_1)$.
%%  \item si $A \neq B$ et $A \neq\Omega$ et $B \neq\Omega$. 
%% La droite $d$ passant par $A$ et par $B$ a donc pour \'equation :\\
%% $X(y_A-y_B)-Y(x_A-x_B)+Z(x_Ay_B-x_By_A)=0$.\\
%% Les abscisses des points d'intersection de $d$ et $\Gamma$ v\'erifient :\\
%% $X(y_A-y_B)-Y(x_A-x_B)+Z(x_Ay_B-x_By_A)=0$ et\\
%% $Y^3-Y^2Z-X^2Z=0$.\\
%% Le coefficient  $k=(x_Ay_B-x_By_A)$ de $Z$ n'est pas nul car les points $A$ 
%% et $B$ ne sont pas confondus et aussi parce que  $A$ et $B$ ne sont pas 
%% align\'es avec (0,0,1). Puisque (0,0,1) est exclu on peut diviser par 
%% $X^2+Y^2$ et on a :\\
%% $-k*Z=-k*Y^3/(X^2+Y^2)=X(y_A-y_B)-Y(x_A-x_B)$\\
%% Donc $X$ et $Y$ v\'erifient une \'equation homog\`ene du 3i\`eme degr\'e :\\
%% $((x_A-x_B)-k)*Y^3+X^2Y(x_A-x_B)-Y^2X(y_A-y_B)-X^3(y_A-y_B)=0$\\
%% dans cette \'equation les coefficients de $X^3$ et de $Y^2X$ sont les m\^emes
%% donc :\\
%% - soit $Y=0$ est solution, on a alors  $-X^3(y_A-y_B)=0$ et comme
%% (0,0,1) est exclu c'est que $(y_A-y_B)=0$ c'est \`a dire $A$ et $B$ 
%% sym\'etriques par rapport \`a l'axe des $y$. On a donc $A*B=\Omega$
%% - soit $Y=0$ n'est pas solution, on pose alors $X/Y=a$ et l'\'equation a 3 
%% racines $a_1,a_2,a_3$ qui v\'erifient :\\
%% $a_1a_2+a_1a_3+a_2a_3=1$.\\
%% On a par exemple $a_1=x_A/y_A$,$a_2=x_B/y_B$, donc
%% $a_3=X_C/Y_C=(1-a_1a_2)/(a_1+a_2)$ puisque  $A$ et $B$ ne sont pas
%%  sym\'etriques par rapport \`a l'axe des $y$ on a $(a_1+a_2)\neq 0$.\\
%%  Donc 
%% $$X_D/Y_D=(a_1a_2-1)/(a_1+a_2)$$
%% Si on pose $f(t)=t(t^2+1)$ et $g(t)=t^2+1$.
%% Si $A$ et $B$ sont deux points de $\Gamma$ diff\'erents de $\Omega$ et non
%%  sym\'etriques par rapport \`a l'axe des $y$, on pose
%% $x_A/y_A=a_1$ et $x_B/y_B=a_2$
%% alors $A$ est le point $f(a_1),g(a_1)$ et $B$ est le point $f(a_2),g(a_2)$,
%% et $D=A*B$ est le point $f(a_3),g(a_3)$ avec $a_3=(a_1a_2-1)/(a_1+a_2)$.\\
%% On sait que :\\
%% $\cot(\theta_1+\theta_2)=(\cot(\theta_1)\cot(\theta_2)-1)/(\cot(\theta_1)+\cot(\theta_2))$\\
%% Si on pose :\\
%% $a_1=x_A/y_A=\cot(\theta_1)$ avec $\theta_1 \in [0;\pi[$\\
%% $a_1=x_A/y_A=\cot(\theta_1)$ avec $\theta_1 \in [0;\pi[$\\
%% Alors $D=A*B$ est le point de $\Gamma$ tel que 
%% $a_3=x_D/y_D=(a_1a_2-1)/(a_1+a_2)=\cot(\theta_1+\theta_2)$\\
%% donc
%% $D=r(\theta_1+\theta_2)$\\
%% \end{itemize}

%% En R\'esum\'e:\\
%% $\Omega$ est l'\'el\'ement neutre,
%% Le sym\'etrique $A1$ de $A$  par rapport \`a l'axe des $y$ est l'inverse de 
%% $A$ pour la loi * ($A*A1=\Omega$).\\
%% Si $r(\theta)=1/\sin(\theta)^3$ et si\\
%% $A=r(\theta_1)$, $B=r(\theta_2)$ alors $A*B=r(\theta_1+\theta_2)$.\\


%% On munit la droite projective $\mathbb R \cup \infty$ de la loi $°$ 
%% d\'efinie par :\\
%% $\infty°\infty=\infty$\\
%% $a°\infty=\infty°a=a$ pour tout $a \in \mathbb R$\\
%% $a°(-a)=\infty$ pour tout $a \in \mathbb R$\\
%% $a°b=(ab-1)/(a+b)$ pour tout $a\in \mathbb R$ et tout $b\in \mathbb R-\{-a\}$\\
%% Cette loi munit $\mathbb R \cup \infty$ d'une structure de groupe commutatif.\\
%% En effet cette loi est associative car :\\
%% $(a°b)°c=((ab-1)/(a+b))°c=((abc-c)/(a+b)-1)/((ab-1)/(a+b)+c)$\\
%% Donc $(a°b)°c=(abc-c-a-b)/(ab+ac+bc-1)$ qui est sym\'etrique en $a,b,c$ ce qui
%% prouve l'associativit\'e.\\
%% Avec {\tt Xcas} on tape :\\
%% {\tt f(a,b):=ifte(a!=-b,(a*b-1)/(a+b),infinity)}
%% {\tt normal(f(f(a,b),c))}\\
%% On obtient :\\
%% {\tt(a*b*c-a-b-c)/(a*b+a*c+b*c-1)}\\
%% Il y a un \'el\'ement neutre $\infty$\\
%% tous les \'el\'ements ont un inverse puisque $a°(-a)=\infty$ et 
%% $\infty°\infty=\infty$.\\
%% L'application $F$ de $(\Gamma,*)$ sur $\mathbb R \cup \infty,°$ d\'efinie 
%% par :\\
%% $F(\Omega)=\infty$
%% $M\in \gamma$ est de coordonn\'ees $x_M,y_M$,($y_M$ est donc non nul)  
%% $F(M)=x_M/y_M$
%% alors $F$ est un isomorphisme de groupe.
%% En effet, 
%% $F$ est bijective car \`a tout \'el\'ement $a$ de 
%% $\mathbb R\cup \infty$, il existe un 
%% point unique $A$ de $\Gamma$ tel que $F(A)=a$ (si $a=\infty$ $A=\Omega$ et
%% sinon $A$ est l'intersection de la 
%% droite $x=a*y$ avec $\gamma$) et on a , \\
%% pour $A$ et $B$ sym\'etriques par rapport l'axe des $y$, 
%% $F(A*B)=F(\Omega)==\infty=a_1°(-a_1)=F(A)°F(B)$ et sinon\\
%% $F(A*B)=F(D)=X_D/Y_D=(a_1a_2-1)/(a_1+a_2)=a_1°a_2=F(A)°F(B)$\\

%% On peut aussi consid\'erer la fonction $G$ de $(\Gamma,*)$ sur 
%% $[0;\pi[ +\bmod \pi$ qui est d\'efinie par :\\
%% si $A=\Omega$ alors $G(A)=0$\\
%% si $A\in gamma$, alors $A=(x_A,y_A)$ et 
%% $G(A)=arg(x_A+i*y_A)=\theta_A \in [0,\pi[$ 
%% la fonction $G$ est bijective car \`a $\theta_A \in [0,\pi[$ il existe un seul 
%% point $A in \Gamma$ c'est le point de coordonn\'ees  homog\`enes
%% $\cos(\theta_A),\sin(\theta_A),\sin(\theta_A)^3$ et\\
%% $G(A*B)=G(D)=\theta_A+\theta_B \bmod \pi=G(A)+G(B) \bmod \pi$

%% Les points $M$ d'ordre 6 v\'erifient $M*M*M*M*M*M=\Omega$. ou 
%% $a°a°a°a°a°a=\infty$.\\
%% $\infty$ est donc un point d'ordre 6.\\
%% On sait que $(0,1)$ est un point d'ordre 2 donc un point d'ordre 6.\\
%% Si $a\in \mathbb R*$ est un point d'ordre 6 on calcule :\\
%% $a°a=(a^2-1)/(2a)$, puis $d:=a°a°a=(a^3-3a)/(3a^2-1)$ et $d°d$\\
%% Il faut calculer pour quelles valeurs de $a$ le d\'enominateur de $d°d$
%% s'annule.\\
%% Avec {\tt Xcas} on tape :\\
%% {\tt f(a,b):=ifte(a!=-b,(a*b-1)/(a+b),infinity)}
%% {\tt d:=normal(f(f(a,a),a))}\\
%% On obtient :\\
%% {\tt (a\verb|^|3-3*a)/(3*a\verb|^|2-1)}\\
%% Donc si $3*a^2-1=0$ on aura les points d'ordre 3 i.e lorsque $a$ vaut 
%% $-\sqrt 3,1/\sqrt3$. Ces valeurs correspondent aux points de coordonn\'ees 
%% $(x,y)$ v\'erifiant : $y^2=3x^2$ et $y^3=x^2+y^2$ c'est \`a dire
%% les points $(-4\sqrt 3/9,4/3)$, $(4\sqrt 3/9,4/3)$\\

%% On tape :\\
%% {\tt factor(f(d,d))}\\
%% On obtient :\\
%% {\tt ((a\verb|^|2+4*a+1)*(a\verb|^|2-4*a+1)*(a+1)*(a-1))/(2*(3*a\verb|^|2-1)*(a\verb|^|2-3)*a)}\\
%% Les valeurs $a$ d'ordre 6 sont :\\
%% $\sqrt 3,-\sqrt 3,1/\sqrt3,-1/\sqrt3,0$\\
%% Ces valeurs correspondent aux points de coordonn\'ees $(x,y)$ v\'erifiant :\\
%% - soit $x^2=3y^2$ et $y^3=x^2+y^2$ \\
%% \'equivalent \`a $x^2=3y^2$ et $y=4$ ou encore $x^2=48$ et $y=4$\\
%% - soit $x^2=y^2/3$ et $y^3=x^2+y^2$ \\
%% \'equivalent \`a $x^2=y^2/3$ et $y=4/3$ ou encore $x^2=16/27$ et $y=4/3$\\
%% - soit $x=0$ et $y^3=x^2+y^2$ \\
%% \'equivalent \`a $y^3=y^2$ ou encore $x=0$ et $y=1$ (puisque $(0,0)$ est exclu).\\
%% Il y a donc 6 points d'ordre 6:\\
%% $\Omega$, $(0,1)$, $(-4\sqrt 3,4)$, $(4\sqrt 3,4)$, $(-4\sqrt 3/9,4/3)$,
%% $(4\sqrt 3/9,4/3)$.
%% Ou encore plus simplement :\\
%% On cherche les \'el\'ements d'ordre 6 dans $[0;\pi[\ \bmod\ \pi$ .\\
%% Si $M^6=0$ c'est que $6*arg(M)=0 \bmod \pi$,
%% donc l'argument de $M$ vaut $0$ ou $\pi/6$ ou $\pi/3$ ou $\pi/2$ ou $2\pi/3$ 
%% ou $5\pi/6$ .
\end{enumerate}

\end{enumerate}

\section{Partie V}
{\em Dans cette partie, on \'etudie $\Gamma'$ d\'efinie dans le plan 
 $\mathbb F_{16}^2$ par :
\[ P(x,y)=-y^2-y+(x^3+x)=0 \]
}
\begin{enumerate}
\item
{\em Montrer que la courbe $\Gamma'$ contient au plus 32 points de
$\mathbb F_{16}^2$.}

\`A chaque $a \in \mathbb F_{16}$ il correspond deux valeurs au plus de 
$b \in \mathbb F_{16}$ v\'erifiant $b^2+b=d=a^3+a$ puisqu'il s'agit
d'une équation de degré 2 sur un corps. \\
%% En effet, si dans $\mathbb F_{16}$, on a $b^2+b=d$
%% l'\'equation en $y$ $y^2+y=b^2+b=d$ a une solution $y=b$ et on a :\\
%% $y^2+y=b^2+b$ ou $(y+b)(y+b+1)=0$ et donc si $b$ est solution, $b+1$ est aussi
%% solution. Ainsi, dans $\mathbb F_{16}$, l'\'equation en $y$ $y^2+y=d$ a soit 0,
%% soit 2 solutions distinctes de somme 1.\\
Comme $\mathbb F_{16}$ a 16 \'el\'ements,
la courbe $\Gamma'$ contient 
au plus 2*16=32 points.
 
\item {\em
On introduit le polyn\^ome homog\`ene :
\[ \overline P(X,Y,Z)=X^3+XZ^2-Y^2-YZ^2 \]
D\'efinir un point \`a l'infini $\Omega$ et une multiplication interne 
dans $\Gamma=\Gamma'\cup \Omega$.}

Le point $\Omega$ correspond \`a $Z=0$ et doit v\'erifier
$\overline P(X,Y,0)=X^3=0$ donc on prend $\Omega$ 
correspondant au point de coordonn\'ees homog\`enes (0,1,0), 
le point \`a l'infini dans la direction de l'axe des $y$.

Par analogie avec la partie IV, $\Omega$ sera l'élément neutre
de la loi.

On remarque que si $b$ est une solution de $y^2+y=d$ alors $b+1$ est aussi 
solution de $y^2+y=d$. Donc
la droite $x=a \in \mathbb F_{16}$ coupe la courbe 
$\Gamma$ en 1 ou 3 points qui sont $\Omega$ et \'eventuellement 
$(a,b)$ et $(a,b+1)$  lorsque l'\'equation $y^2+y=a^3+a$ 
admet une solution $y=b$ dans $\mathbb F_{16}$. L'inverse
de $(a,b) \in \Gamma'$ sera donc $(a,b+1)$ (qui est aussi dans $\Gamma'$).

L'intersection d'une droite $y=mx+p$ avec $\Gamma'$ est donnée par
une équation du 3ème degré sur $\F_{16}$ donc si elle admet 2 solutions,
elle en admet forcément une 3ème. On définit le composé des 2 solutions
comme le symétrique de la 3ème.

Finalement la loi * est définie par :
\begin{itemize}
\item $\Omega*\Omega=\Omega$
\item $(a,b)*\Omega=(a,b)$ si $(a,b) \in \Gamma'$
\item Si la droite $AB$ recoupe $\Gamma$ en $C=(c_1,c_2)$, on pose~:
\[ A*B=D=(c_1,c_2+1) \]
\item Le cas $A=B$ est traité plus bas.
\end{itemize}

\item Cette loi est évidemment commutative, admet $\Omega$ comme neutre
et on a $(a,b)^{-1}=(a,b+1)$ pour tout $(a,b)\in \Gamma'$.

\item {\em On se propose de calculer $A^2=A*A$ pour $A=(a,b) \in \Gamma'$.
On cherche la droite $D$ dont l'intersection avec $\Gamma'$ admet
un point double en $A$.}
\begin{enumerate}
\item {\em Montrer que $D$ a pour \'equation :
\[ P'_x(a,b)(x-a)+P'_y(a,b)(y-b)=0 \]
}
Pour $A=(a,b) \in \Gamma'$ on a $P(a,b)=0$, donc~:
\begin{eqnarray*}
 P(x,y)&=&P(x,y)-P(a,b)\\
&=& P(x,y)-P(x,b)+P(x,b)-P(a,b) \\
& = & (y-b) Q(x,y) + (x-a) R(x,y) 
\end{eqnarray*}
en factorisant $y-b$ dans $P(x,y)-P(x,b)$
et $x-a$ dans $P(x,b)-P(a,b)$ (par exemple par la m\'ethode de
Horner). On faisant $x=a$ et en d\'erivant par rapport \`a $y$ puis en
faisant $y=b$, on a $Q(a,b)=P'_y(a,b)$, de m\^eme $R(a,b)=P'_x(a,b)$.
Finalement~:
\[ P(x,y)=(x-a) P'_x(a,b) + (y-b) P'_y (a,b) + P_2(x-a,y-b) \]
où $P_2$ ne contient que des monomes de degré total $\geq 2$.
Donc la droite $D$ d'équation
$(x-a) P'_x(a,b) + (y-b) P'_y (a,b)=0$ et la courbe $\Gamma'$
admettent un point double en commun.

On a $P'_x(a,b)=a^2+1$ et $P'_y(a,b)=1$
donc la tangente \`a $\Gamma'$ en $A$ a pour \'equation~:
\[ (a^2+1)(x-a)+(y-b)=0 \]
ou encore $(a^2+1)x+a^3+a+b=y$ or $a^3+a=b^2+b$, donc
\[ y=(a^2+1)x+b^2 \]

\item {\em D\'eterminer les coordonn\'ees de $A*A$.}

La tangente \`a $\Gamma'$ en $A$ 
recoupe $\Gamma'$ en un point $(x,y)$ qui v\'erifie :
\[ x^3+x=y^2+y=(a^2+1)^2 x^2+b^4+(a^2+1)x+b^2 \]
On calcule le terme en $x^2$ de cette équation en $x$,
on trouve $a^4+1$, or c'est
la somme des 3 racines, et comme $x=a$ est racine double, la
troisième racine est $x=a^4+1$.
Il reste \`a calculer :
\[ y=(a^2+1)(a^4+1)+b^2=a^6+a^4+a^2+1+b^2=a^4+b^4+1 \]
car $a^6+a^2=b^4+b^2$.
La tangente au point $A=(a,b)$ avec  $a^3+a=b^2+b$ coupe $\Gamma'$ en 
$C=(x=a^4+1,y=a^4+b^4+1)$ donc le point $D$ intersection de $\Omega C$ avec
$\Gamma'$ est le point:
\[ D=A*A=(a^4+1,a^4+b^4) \]
Donc si $A=(a,b)$ alors $A*A=(a^4+1,a^4+b^4)$.

\item {\em En d\'eduire que, pour tout point $A$ de $\Gamma'$ on a :
\[ A^4=A^{-1} \]}
On calcule $A^4$ :
\[ A^4=(A*A)*(A*A)=(a^4+1,a^4+b^4)*(a^4+1,a^4+b^4) \]
donc puisque pour tout $a \in \mathbb F_{16}$ on a $a^{15}=1$,
\begin{eqnarray*}
 A^4&=&((a^4+1)^4+1,(a^4+1)^4+(a^4+b^4)^4) \\
 &=&(a+1+1,a+1+a+b) \\
 &=&(a,b+1) \\
 &=&A^{-1} 
\end{eqnarray*}

\item {\em
En d\'eduire le cardinal de $\Gamma$ et sa d\'ecomposition en produit direct
de groupes cycliques.}

$\Gamma$ contient $n$ points avec $n \leq 32$ et $n$ est une puissance de 5 
puisque tous les \'el\'ements sont d'ordre 5, donc $n=1$, $n=5$ ou $n=25$.

Posons pour $\omega \in \mathbb F_{16}$ :
\[ A=(1,0), \quad  B=(\omega^3,\omega^9) \]
On a $A \in \Gamma$ car $0^2+0=1^3+1$ et
$B \in \Gamma$ car $\omega^{18}+\omega^9=\omega^9+\omega^3$ puisque 
$\omega^{15}=1$.

On a :
\[ A=(1,0), \quad A*A=(0,1), \quad A*A*A=(1,0)*(0,1)=(0,0) \]
\[  A*A*A*A=(0,1)*(0,1)=(1,1), \quad A*A*A*A*A=\Omega \]
Donc $B$ n'est pas une puissance de $A$.
Donc $n=25$ et les 25 \`el\'ements sont :
\[ \Omega,A,A^2..A^4,B,B*A..B*A^4,....B^4,B^4*A.B^4*A^4. \]

Avec {\tt Xcas}, on définit l'ensemble $K$ des \'el\'ements du corps 
$\mathbb F_{16}$ :
\begin{center}
{\tt F16:=GF(2,4,['t','F16']);}\\
{\tt w:=F16(t);}\\
{\tt K:=append(seq(w\verb|^|k,k,1,15),F16(0)):;} 
\end{center}
On tape pour avoir les valeurs de $a^3+a$ pour $a\in \mathbb F_{16}$ :
\begin{center}
{\tt La:=seq(K[k]\verb|^|3+K[k],k,0,15)}
\end{center}
On obtient :
\begin{center}
{\tt [F16(t\verb|^|3+t),F16(t\verb|^|3+t+1),F16(t\verb|^|3+t\verb|^|2+1),F16(t\verb|^|3+t),}\\
{\tt F16(t\verb|^|3+t),F16(t\verb|^|2+t+1),F16(t\verb|^|3),F16(t\verb|^|3+t+1),F16(t\verb|^|2+t),}\\
{\tt F16(t\verb|^|3+t+1),F16(t\verb|^|2+1),F16(t\verb|^|3+t\verb|^|2),F16(t+1),}\\
{\tt F16(t\verb|^|3+t\verb|^|2+t+1),F16(0),F16(0)]}
\end{center}
On tape pour avoir les valeurs diff\'erentes de $a^3+a$ pour 
$a\in \mathbb F_{16}^*$~:
\begin{center}
{\tt A:=set[op(La)];}\\
{\tt size(A);}
\end{center}
On obtient 11 valeurs diff\'erentes~:
\begin{center}
{\tt set[F16(t\verb|^|3+t),F16(t\verb|^|3+t+1),F16(t\verb|^|3+t\verb|^|2+1),F16(t\verb|^|2+t+1),}\\
{\tt F16(t\verb|^|3),F16(t\verb|^|2+t),F16(t\verb|^|2+1),F16(t\verb|^|3+t\verb|^|2),}\\
{\tt F16(t+1),F16(t\verb|^|3+t\verb|^|2+t+1),F16(0)]}
\end{center}

Pour chacune de ces valeurs $a$ l'\'equation $y^2+y=a$ a-t-elle 
des solutions ?

On tape pour avoir les valeurs de $b^2+b$ pour $b\in \mathbb F_{16}$ :
\begin{center}
{\tt Lb:=seq(K[k]\verb|^|2+K[k],k,0,15)}
\end{center}
On obtient :
\begin{center}{\tt [F16(t\verb|^|2+t),F16(t\verb|^|3+t\verb|^|2+1),F16(t\verb|^|2+t+1),F16(t\verb|^|2+t+1),F16(1),\\
F16(t\verb|^|3+t\verb|^|2),F16(t\verb|^|3+t+1),F16(t\verb|^|3+t\verb|^|2),F16(t\verb|^|3+t\verb|^|2+1),F16(1),\\F16(t\verb|^|3+t),F16(t\verb|^|2+t),F16(t\verb|^|3+t+1),F16(t\verb|^|3+t),F16(0),F16(0)]}\end{center}
On tape pour avoir les valeurs diff\'erentes de $b^2+b$ pour 
$b\in \mathbb F_{16}$ :
\begin{center}
{\tt B:=set[op(Lb)];}\\
{\tt size(B);}
\end{center}
On obtient 8 valeurs diff\'erentes :
\begin{center}
{\tt set[F16(t\verb|^|2+t),F16(t\verb|^|3+t\verb|^|2+1),F16(t\verb|^|2+t+1),F16(1),}\\
{\tt F16(t\verb|^|3+t\verb|^|2),F16(t\verb|^|3+t+1),F16(t\verb|^|3+t),F16(0)]}
\end{center}
Comme 2*8=16 cela prouve que dans $\mathbb F_{16}$ l'\'equation en $y$, 
$y^2+y=d$ n'a pas de solutions doubles
(on peut aussi le voir en faisant la somme des racines).

On tape pour avoir les valeurs communes de $a^3+a$ et de $b^2+b$ pour 
$a\in \mathbb F_{16}^*$ et $b\in \mathbb F_{16}$:
\begin{center}
{\tt C:= A intersect B;}\\
{\tt size(C);}
\end{center}
On obtient 7 valeurs diff\'erentes :
\begin{center}
{\tt set[F16(t\verb|^|3+t),F16(t\verb|^|3+t+1),F16(t\verb|^|3+t\verb|^|2+1),F16(t\verb|^|2+t+1),\\
F16(t\verb|^|2+t),F16(t\verb|^|3+t\verb|^|2),F16(0)]}
\end{center}

On compte le nombre de solutions dans $\mathbb F_{16}$ de l'\'equation en $x$, 
$x^3+x=d$  lorsque $d \in ${\tt La}.
On tape :
\begin{center}
{\tt seq(count\_eq(C[p],La),p,0,6)} 
\end{center}
On obtient {\tt [3,3,1,1,1,1,2]}.
Les 7 valeurs diff\'erentes de $a^3+a$ sont donc 
obtenues pour 3+3+1+1+1+2=12 valeurs de $a$ lorsque $a\in \mathbb F_{16}$,
à chaque $a$ correspond alors 2 valeurs de $b$, ce qui nous donne
bien 24 éléments dans $\Gamma'$ et $\Gamma$ contient 25 points.

{\bf Remarques}
\begin{itemize}
\item {\tt 3} indique que l'\'equation en $x$, 
$x^3+x=d$  lorsque $d \in${\tt La} a 3 racines distinctes,
\item
{\tt 2} indique que l'\'equation en $x$, 
$x^3+x=d$  lorsque $d \in${\tt La} a 3 racines dont une racine double,
\item
{\tt 1} indique que l'\'equation en $x$, 
$x^3+x=d$  lorsque $d \in ${\tt La} a 1 racine simple ou 1 racine triple.
\end{itemize}

On peut \'ecrire le programme qui va calculer $A*B$ pour 2 \'el\'ements
 diff\'erents $A=(xa,ya)$ et $B=(xb,yb)$ de $\Gamma$. 

\'Equation de la droite $AB$:
\[ (ya+yb)*x+(xa+xb)*y+xa*yb+xb*ya=0 \]
si $xa \neq xb$ alors $xa+xb$ est inversible. Son inverse est :
$(xa+xb)^{14}$ puisque $(xa+xb)^{15}=1$.
Donc
\[ y=(xa+xb)^{14}*((ya+yb)*x+xa*yb+xb*ya) \]
Donc le coefficient de $x^2$ lorsque l'on a remplacé $y$ en fonction de $x$ 
dans $x^3+x+y^2+y$ est :
\[ (xa+xb)^{28}*(ya+yb)^2=(xa+xb)^{13}*(ya^2+yb^2) \]
On a $xa,xb,xc$ v\'erifient :
\[
x^3+(xa+xb)^{13}*(ya^2+yb^2)*x^2+....=0
\]
La somme des racines $S$ v\'erifie :
\[ S=(xa+xb)^{13}*(ya^2+yb^2) \]
donc
\[ S=xa+xb+xc=(xa+xb)^{13}*(ya^2+yb^2) \]
donc
\begin{eqnarray*}
xc&=&(xa+xb)^{13}*(ya^2+yb^2)+xa+xb \\
yc&=&(xa+xb)^{14}*((ya+yb)*xc+xa*yb+xb*ya) \\
xd&=&xc \\
yd&=&yc+1
\end{eqnarray*}
si $xa==xb$ avec $ya \neq yb$ alors $etoile(xa,ya,xb,yb)=\Omega$\\
On tape pour d\'efinir la loi {\tt etoile} de 2 \'el\'ements de $\Gamma$ en
notant $\Omega$ {\tt infinity} :\\
\begin{verbatim}
// F16:=GF(2,4,['t','F16'])
// xa et ya sont dans F16 par ex xa:=F16(w^3) ...
estdansgamma(xa,ya):=(xa^3+xa+ya^2+ya==0);

// a:=[xa,ya] b:=[xb,yb] ou xa,ya,xb,yb sont dans F16
etoile(a,b):={
 local xa,xb,ya,yb,xc,yc;
 if (a==infinity and b==infinity) return infinity;
 if (a==infinity) {
  if (estdansgamma(op(b))==0) return "b pas dans gamma";
  return b;
 }
 if (b==infinity) {
  if (estdansgamma(op(a))==0) return "a pas dans gamma";
  return a;
 }
 xa:=a[0]; xb:=b[0]; ya:=a[1]; yb:=b[1];
 if (estdansgamma(xa,ya)==0) return "a pas dans gamma"; 
 if (estdansgamma(xb,yb)==0) return "b pas dans gamma";
 if (xa!=xb) {
  xc:=(xa+xb)^13*(ya^2+yb^2)+xa+xb;
  yc:=(xa+xb)^14*((ya+yb)*xc+xa*yb+xb*ya)+F16(1);
  return [xc,yc];
 }
 if ((xa==xb) and (ya==yb)) {
  xc:=xa^4+F16(1);
  yc:=xa^4+ya^4;
  return [xc,yc];
 }
 return infinity;
}:;
\end{verbatim}
On tape :
\begin{center}
{\tt u:=[F16(1),F16(0)]} \\
{\tt v:=[w\verb|^|3,w\verb|^|9]}
\end{center}
On sait que :
{\tt u} est dans $\Gamma$ et que :
{\tt v} est dans $\Gamma$.

On tape pour avoir les 25 \'el\'ements de $\Gamma$ :
\begin{verbatim}
G:=seq(seq(etoile(
  puissrapide(u,k,etoile,infinity,0),
  puissrapide(v,j,etoile,infinity,0)
 ),k=1..5),j=1..5):;
G:=[G];
\end{verbatim}
On obtient :
\begin{center}
{\tt [[F16(t+1),F16(t\verb|^|3+t\verb|^|2+t)],[F16(t\verb|^|3+t\verb|^|2+t),F16(t\verb|^|2+t+1)],}\\
{\tt [F16(t\verb|^|3+t+1),F16(t\verb|^|3+t\verb|^|2)],[F16(t\verb|^|2),F16(t\verb|^|2+t+1)],}\\
{\tt [F16(t\verb|^|3),F16(t\verb|^|2+1)],[F16(t\verb|^|3+t),F16(t\verb|^|2+t)],[F16(t\verb|^|3+1),}\\
{\tt F16(t\verb|^|3+t\verb|^|2)],[F16(t\verb|^|3+t\verb|^|2+t+1),F16(t\verb|^|3)],[F16(t\verb|^|2+1),}\\
{\tt F16(t)],[F16(t),F16(t\verb|^|3+t\verb|^|2)],[F16(t\verb|^|2+1),F16(t+1)],}\\
{\tt [F16(t\verb|^|3+t\verb|^|2+t+1),F16(t\verb|^|3+1)],[F16(t\verb|^|3+1),}\\
{\tt F16(t\verb|^|3+t\verb|^|2+1)],[F16(t\verb|^|3+t),F16(t\verb|^|2+t+1)],[F16(t),}\\
{\tt F16(t\verb|^|3+t\verb|^|2+1)],[F16(t\verb|^|2),F16(t\verb|^|2+t)],[F16(t\verb|^|3+t+1),}\\
{\tt F16(t\verb|^|3+t\verb|^|2+1)],[F16(t\verb|^|3+t\verb|^|2+t),F16(t\verb|^|2+t)],}\\
{\tt [F16(t+1),F16(t\verb|^|3+t\verb|^|2+t+1)],[F16(t\verb|^|3),F16(t\verb|^|2)],}\\
{\tt [F16(1),F16(0)],[F16(0),F16(1)],[F16(0),F16(0)],}\\
{\tt [F16(1),F16(1)],infinity]}
\end{center}
On tape :
\begin{center}
{\tt size(set[op(G)])}
\end{center}
On obtient :
\begin{center}
{\tt 25}
\end{center}
\end{enumerate}

\item {\em
Indiquer bri\`evement comment implanter un syst\`eme de cryptographie du 
type de celui de la partie II \`a l'aide de $\Gamma$.}

Comme on n'a que 25 \'el\'ements pour coder les 26 lettres de 
l'alphabet, on peut convenir de dire que :
$A$ sera cod\'ee par 0, $B$ sera par 1, ..., 
les lettres $V$ et $W$ seront cod\'ees par 21,
$X$ sera cod\'ee par 22,
les lettres $I$ et $Y$ seront cod\'ees par 7, $Z$ par 23,
l'espace sera cod\'e par 24.\\
Les \'el\'ements de $G$ seront indic\'es par 0..24.
On \'ecrit la  fonction de codage {\tt lettre2n} qui convertit une lettre 
majuscule en un entier entre 0  et 24 et de d\'ecodage {\tt n2lettre} qui 
convertit un entier entre 0 et 24 en une lettre majuscule :
\begin{verbatim}
lettre2n(a):={
 local c;
 c:=op(asc(a));
 if (c==32) return 24;
 if (c<87) return c-65;
 if (c==87) return 21;
 if (c==88) return 22;
 if (c==89) return 7;
 if (c==90) return 23;
}:;

n2lettre(n):={
 if (n<22) return char(n+65);
 if (n==24) return " ";
 if (n==22) return "X";
 if (n==23) return "Z";
}:;
\end{verbatim}
Puis on \'ecrit la fonction qui code une lettre par un \'el\'ement de $G$ :
\begin{verbatim}
//a est un caractere majuscule
lettre2G(a,G):={
 local c;
 c:=lettre2n(a);
 return G[c];
};
\end{verbatim}
On suppose le groupe $G$ ainsi que les \'el\'ements $\pi$ et $\alpha$ 
de $G$ connus de tous.
On garde secret l'entier $e$ et $\alpha=\pi^{e}$. Avec {\tt Xcas} $\pi$ sera 
not\'e {\tt pii}, $e$ sera not\'e {\tt ex} et $\alpha$ sera not\'e {\tt alpha},
par exemple :
\begin{center}
{\tt pii:=G[10]}\\
{\tt ex:=3} \\
{\tt alpha:=puissrapide(pii,ex,etoile,infinity,0)}
\end{center}
La fonction $f_\alpha$, not\'ee {\tt falpha} sera d\'efinie par~:
\begin{verbatim}
// tau est un element de G par exemple tau:=lettre2G("A",G)
// falpha(k,tau) renvoie une matrice 2*2 d'elements de F16
falpha(k,tau):={
 local a;
 return [puissrapide(pii,k,etoile,infinity,0), 
         etoile(puissrapide(alpha,k,etoile,infinity,0),tau)];
}:;
\end{verbatim}
La fonction $\phi_e$ sera alors {\tt phie}~:
\begin{verbatim}
// a et b sont des elements de G
//inva:=a^(5-ex) est l'inverse de a^ex car a^5=1
phie(a,b,ex):={
 local inva;
 ex:=irem(ex,5);
 inva:=puissrapide(a,5-ex,etoile,infinity,0);
 return etoile(inva,b);
}:;
\end{verbatim}
Voici enfin la fonction de codage d'une chaine de caract\`eres :
\begin{verbatim}
//s est une chaine de caracteres majuscules
//on choisit k de facon aleatoire
codage(s,G):={
 local L,n,j,k,f;
 L:=[];
 n:=size(s);
 for (j:=0;j<n;j++){
  k:=rand(25);
  f:=falpha(k,lettre2G(s[j],G));
  L:=append(L,f);
 }
 return L;
};
\end{verbatim}
et la fonction de d\'ecodage :
\begin{verbatim}
//indice d'un element tau de G
indice(tau,G):={
 local n,k;
 n:=size(G);
 k:=0;
 while (tau!=G[k]){
  k:=k+1;
 }
 return k;
}:;

//decodage d'une liste L envoyee par la fonction codage
//ex et l'element tenu secret
decodage(L,ex,G):={
 local n,j,M,tau,k,a,b;
 M:="";
 n:=size(L);
 for (j:=0;j<n;j++){
  a:=L[j,0];
  b:=L[j,1];
  tau:=phie(a,b,ex);
  k:=indice(tau,G);
  M:=M+n2lettre(k);
 }
 return M;
}:;
\end{verbatim}
On reprend l'exemple de la partie I, on tape
\begin{center}
{\tt message:=codage("COGITO",G)}
\end{center}
on obtient une "matrice" de couples de $\F_{16}$ que l'on peut d\'ecoder
en tapant~:
\begin{center}
{\tt decodage(message,ex,G)}
\end{center}

\end{enumerate}

\end{document}