\documentclass[11pt,a4paper]{article}
\usepackage{multicol}
\usepackage[french]{babel}
\newfont{\mini}{cmssi10 scaled 480}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\euro{\mbox{\textsf{C}\kern -2.33em{\raise0.24ex\vbox{\small\it =}}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\fin{\nolinebreak \raise-0.1em\hbox{$\Box$}}
\def\stackunder#1#2{\mathrel{\mathop{#2}\limits_{#1}}}
\def\dual{ ^{\rm v}}
\def\bidual{ ^{\rm vv}}
\def\primedual{ ^{\prime \rm v}}
\def\ideal{{\cal J}}
\def\LL{{\cal L}}
\def\max{{\cal M}}
\def\quot#1#2{\mbox{\raise 0.1cm\hbox{$#1$}{\big /}\raise -0.1cm\hbox{$#2$}}}
\def\danger{{\Large \bf
    $\bigtriangleup$}\kern-0.32cm\raise0.05cm\hbox{\small
    !}\kern0.32cm\lower0.05cm\hbox{}}
%%%%%%%
\newlength{\largeurtmp}
\def\rela{\settoheight{\largeurtmp}{Z}{\rm Z} \kern -0.6\largeurtmp
  \raise 0.05cm\hbox{\tiny{\it /}}\kern 0.6\largeurtmp}
\def\petitrela{\settoheight{\largeurtmp}{Z}{\rm Z} \kern -0.4\largeurtmp
  \raise 0.05cm\hbox{\tiny{\it /}}\kern 0.4\largeurtmp}
\def\petitcomplex{{
    \settoheight{\largeurtmp}{$_C$}{\rm C}\kern -\largeurtmp
    \rule{0.25pt}{1.3\largeurtmp}\kern \largeurtmp}}
\def\complex{{
    \settoheight{\largeurtmp}{Q}{\rm C}\kern -0.66\largeurtmp
    \rule{0.25pt}{0.9\largeurtmp}\kern 0.66\largeurtmp}}
\def\ratio{{
    \settoheight{\largeurtmp}{C}{\rm Q}\kern -0.75\largeurtmp
    \rule{0.25pt}{0.9\largeurtmp}\kern 0.75\largeurtmp}}
\def\petitratio{{
    \settoheight{\largeurtmp}{C}{\rm Q}\kern -0.6\largeurtmp
    \rule{0.25pt}{0.6\largeurtmp}\kern 0.6\largeurtmp}}
\newcommand{\proj}{{\rm I} \! {\rm P}}
\newcommand{\reel}{{\rm I} \! {\rm R}}
\newcommand{\Fp}{{\rm I} \! {\rm F}_p}
\newcommand{\nat}{{\rm I} \! {\rm N}}
%%%%%%%%%%%%%%%Debut de macros de fiches d'exos
%%les macros sont \exo, \qu, \quskip \squ \qusqu \qusquskip
\newcounter{exo}
\newcounter{question}
\newlength{\lng}
\newcounter{sousquestion}
\setcounter{exo}{1}
\def\exo{

  \bigskip
  \noindent{\bf Exercice
    \Roman{exo}:}\addtocounter{exo}{1}\setcounter{question}{0}\nopagebreak 

  }
\def\exotitre#1{

  \bigskip
  \noindent{\bf Exercice
    \Roman{exo}: #1}\addtocounter{exo}{1}\setcounter{question}{0}\nopagebreak 

  }
\def\qu{

  \addtocounter{question}{1}\arabic{question})
  \setcounter{sousquestion}{1} }
\def\quskip{

  \bigskip
  \qu}
\def\squ{

  \settowidth{\lng}{\arabic{question})
  }\hspace{\the\lng}\alph{sousquestion}) \addtocounter{sousquestion}{1}} 
\def\qusqu{\qu\nopagebreak \vskip -1\baselineskip \squ}
\def\qusquskip{\quskip\nopagebreak \vskip -1\baselineskip \squ}

%%reference pour exos,squ {\`a} placer avant la question, qu est a placer apres
\def\labelexo#1{\expandafter\edef\csname refexo#1\endcsname {\Roman{exo}}}
\def\refexo#1{\csname refexo#1\endcsname}
\def\labelqu#1{\expandafter\edef\csname refqu#1\endcsname {\arabic{question})}}
\def\refqu#1{\csname refqu#1\endcsname}
\def\labelsqu#1{\expandafter\edef\csname refsqu#1\endcsname
  {\arabic{question}\alph{sousquestion})}} 
\def\refsqu#1{\csname refsqu#1\endcsname}  

%%%%%%%%%%fin de macros fiche d'exos
%%macros taille page
\newlength{\elargir}
\setlength{\elargir}{2.5cm}
\addtolength{\leftmargin}{-\elargir}
%%\addtolength{\hoffset}{-\elargir}
\addtolength{\oddsidemargin}{-\elargir}
\addtolength{\evensidemargin}{-\elargir}
\addtolength{\elargir}{\elargir}
\addtolength{\textwidth}{\elargir}
\addtolength{\textheight}{14\baselineskip}
\topmargin=-6\baselineskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%        
\everymath={\displaystyle}
\begin{document}
\noindent{\bf Universit{\'e} de Paris 7 \hfill \framebox{\Large \bf
    \hspace{ 1cm} TP23 Polyn{\^o}mes et Codes \hspace{1cm}}\hfill   agreg 2011 (F.Han\footnote{http://www.math.jussieu.fr/$\sim$han/agreg})}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\code#1{{\tt #1}}
%% 
\columnsep 0.7cm
\begin{multicols}{2}
% restart;maple_mode(0);cas_setup(0,0,0,1,0,1e-10,10,[1,50,0,25],0,0,0); //radians,pas de cmplx, pas de  Sqrt
\exotitre{Codes de Golay; r{\'e}sidus quadratiques}
\newcommand{\F}{{\rm I} \! {\rm F}}
\qu Nous allons {\'e}tudier le code de Golay $G_{23}$, qui est un code cyclique en
caract{\'e}ristique $2$, de longueur $23$. Il est de plus $3$ correcteur parfait.
\squ En factorisant $x^{23}-1$ dans $\rela/2\rela[x]$ on trouve deux facteurs
irr{\'e}ductibles de degr{\'e} $11$. On en choisit un, not{\'e} $g$.
% factor(x^23-1%2);
% g:=op(factor(x^23-1%2))[1];
\squ Comment peut on obtenir la liste des facteurs d'un polyn{\^o}me dans
$\rela/2\rela[x]$?  
% !s!<c>
%Astuce: pour recuperer directement le second facteur, on peut utiliser op, ou
%bien on utilise factors.
%!s!
% factors(x^23-1%2);//donne un resultat modulaire ( % 0 pour revenir dans ZZ)
\squ Pourquoi les racines de
$g$ sont elles  d'ordre 23? Combien y a t'il de carr{\'e}s dans
$(\rela/23\rela)^\times$? Lesquels? En d{\'e}duire que $x^{23}-1$ avait forc{\'e}ment
des diviseurs de degr{\'e} $11$ dans $\rela/2\rela[x]$. Exprimer les racines de $g$
en fonction d'une. (On prouvera ces r{\'e}sultats de mani{\`e}re th{\'e}orique, en utilisant
le frobenius, et on illustrera ces r{\'e}sultats en prenant une racine de $g$ dans
$\F_{2^{11}}$. 
%!s!<c>
%On ne peut pas creer F2[x]/g avec GF car les racines de g ne sont pas
%primitives dans (F_2^11) puisqu'elles sont d'ordre 23, et la commande GF veut
%un polynome irreductible dont les racines engendre le groupe multiplicatif du
%corps voulu. 
%!s!
%purge(a,FF); // pour eviter les Pb dans la ligne suivante.
%FF:=GF(2,11,['a','FF']);
%!s!<c>
% Attention a ne pas melanger le modulaire %2 et FF(a) sinon ca plante (version
% 0.9.1)
% Pour remedier a cela on utilise g%0
%!s!
%factor(g%0,FF(a));
%!s!<c>
%On note t la premiere racine de g trouvee dans F2048
%!s!
%t:=subst(op(factor(g%0,FF(a)))[0],x=0);
%!s!<c>
%On va maintenant comparer les racines de g avec les puissances de l'une d'entre
%elles: t. On va illustrer que ce sont les t^i ou i est un carre modulo
%23. On cree la liste des carres avec la fonction ensembles pour simplififer les
%doublons. 
%!s!
%carres:=set[seq(irem(j^2,23) ,j=1..22)];
%P:=1;for j in carres do P:=P*(x-t^j) od;
%normal(P);//On retrouve bien g
%g;
%!s!<c>
%On n'etait pasoblige de trouver une racine de g dans F2^11 defini par GF, on
%pouvait travailler modulo g.
%!s!
%purge(t);
%P:=1%2;for j in carres do P:=P*(x-t^j) od;
%rem(P,subst(g,x=t),t); //On travaille dans F2[t]/(g(t))
\qu On consid{\`e}re le code de Golay $G_{23}$ d{\'e}fini par l'id{\'e}al  $(g)$ de
$\F_2[x]/(x^{23}-1)$ vu comme un $\F_2$ espace vectoriel. (Dans la suite, toutes les
coordonn{\'e}es seront prises dans la base $1,x,\dots,x^{22}$ ) Quel est le nombre
d'{\'e}l{\'e}ments de $G_{23}$? 
% !s!<c>
% G23 a 2^{23-deg(g)} elements. Le cardinal d'une boule de rayon 3 est la somme
% de C_23^i pour i allant de 0 {\`a} 3. L'annulation du terme suivant signifie que
% G23 a les invariants numeriques d'un code binaire 3 correcteur parfait de
% dimension 12 dans un espace vectoriel de dimension 23. 
% !s!
%normal(2^23-add(seq(binomial(23,j),j=0..3))*2^12);
\squ D{\'e}duire de la liste des carr{\'e}s et du crit{\`e}re de minoration de la distance
d'un code cyclique (Cf cours) que $G_{23}$ est de distance au moins 5
% !s!<c>
% il y a 4 entiers consecutifs donc la distance est au moins 5
%!s!
% sort(op(carres));
\squ Donner une matrice g{\'e}n{\'e}ratrice\footnote{ie une base de l'espace
  vectoriel $G_{23}$} de $G_{23}$.
%G:=matrix(12,23,(ii,j)->(coeff(rem(x^(ii)*g,x^23-1,x),x,j)));
\qusqu Donner une matrice g{\'e}n{\'e}ratrice $GE$ du code {\'e}tendu
$\widetilde{G_{23}}$\footnote{On ajoute un bit de   parit{\'e}} de $G_{23}$ 
%GE:=augment(G,transpose(G*[1$23]) mod 2); //le code etendu
\squ Trouver une matrice v{\'e}rificatrice $VE$ de $\widetilde{G_{23}}$. On notera
$\widetilde{G_{23}}^\bot$ le code 
engendr{\'e} par $VE$. (Appel{\'e} code dual de $\widetilde{G_{23}}$).
%VE:=nullspace(GE);
\squ Montrer que $\widetilde{G_{23}}=\widetilde{G_{23}}^\bot$.
% !s!<c>
%Pour montrer que les espaces vectoriels engendr{\'e}s par les lignes de GE et
%celles de VE sont les memes, on cree la matrice M suivante et l'on doit montrer
%qu'elle est de rang 12. On ne dispose pas d'une instruction de rang modulaire,
%on utilise donc Nullspace mod 2
%!s!
% M:=[op(GE),op(VE)];
% dim(nullspace(M));//c'est bien de rang 12
%rank(M);
\squ En d{\'e}duire que si $m$ et $m'$ sont des mots de $\widetilde{G_{23}}$ de
poids\footnote{c'est le nombre de coordonn{\'e}es non nulles} nul modulo $4$  alors
$m+m'$ aussi.\footnote{On remarquera que le produit scalaire $2(m.m')$ est dans
  $4\rela$} 
% !s!<c>
% puisque le code etendu est egal a son dual, on a:
% m.m'=0[2], et donc (m+m').(m+m')=m.m+m'.m' [4]
%Donc si les poids de m et m' sont multiples de 4, celui de m+m' aussi
%On en deduit que le code etendu a une distance multiple de 4, et comme elle
%vaut au moins 5, et qu'il y a des mots de poids 8, c'est 8. Donc celle de G23
%est 7 ou 8, et comme il y a des lignes de poids 7 dans G cette distance vaut 7
%!s! 
\squ Montrer que $\widetilde{G_{23}}$ est de distance $8$ et que $G_{23}$ est de
distance $7$. 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{center}
  {\large \it CF colles non faites TP12}
\end{center}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exotitre{Ecrit 2007}
(Pr{\'e}paration 40min)
% !s!<c>
% -------------------------------------EXERCICE---------------------------------------------
%!s!
\qu Choisir un nombre premier $p$ {\`a} 13 chiffres, tel que \footnote{ou que vous supposez
tel que} le probl{\`e}me
du log discret soit difficile modulo $p$. 
% p:=nextprime(10^13+rand(10000));
\qu Choisir un entier $b$ et un secret $e$ et rendre publique $(b,b^e
[p])$. Commentez votre choix de $b$. 
% !s!<c>
% b,e pas trop petits par rapport a p, pour que le modulo p melange
% vraiment.
%!s!
\qu Remarquer que les lettres $A\dots Z$ ont des codes ASCII
cons{\'e}cutifs. Comment obtenir les codes de chaque lettre d'un mot? (et
si l'on veut que $A$ soit repr{\'e}sent{\'e} par $0$ et $Z$ par $25$?)
% message:="ABCDA, Remarquez que des lettres identiques ne sont pas codees de la meme maniere!";asc(message);
% asc(messsage)-[seq(65,ii=1..length(message))];
\qu Votre voisin choisit un message, tire des $k$ au hasard et code
chaque lettre $x$ avec $(b^k [p],x.(b^e)^k) [p])$ (sans connaitre $e$,
seulement avec $b$ et $b^e$
% b:=12345;e0:=54321; igcd(e0,p-1); B:=powmod(b,e0,p);
% l:=asc(message);k:=[seq(rand(50),j=1..length(message))];
% C:=[seq([irem((b^k[j]),p),irem((l[j]*B^k[j]),p)],j=0..length(message)-1)];//le message crypte
\qusqu D{\'e}coder le message gr{\^a}ce {\`a} $e$.
%ee:=p-1-e0;//c'est -e0 [p-1] qui nous interesse 
% !s!<c>
% L'astuce est que (B^k)=((b^e0)^k) qui vaut par commutativit{\'e}  des la
% composition des application B:x->x^k et A:x->x^e0  ((b^k)^e0). 
%Le principe a retenir, est qu'en crypto on a juste besoin
%d'operations A,B qui  commutent, et que la donnee de A de donne pas
%A^(-1)  
%!s!
% decrypt:=[seq(irem(powmod(C[j][0],ee,p)*C[j][1],p),j=0..length(message)-1)];
% char(decrypt);
\squ Pr{\'e}parer un  expos{\'e} de 20 minutes expliquant la m{\'e}thode et son
int{\'e}r{\^e}t. (temps pour crypter, d{\'e}cryper avec et sans $e$. Statitiques
sur les lettres du message crypt{\'e}...)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 


\newpage
\end{multicols}

\end{document}

