\documentclass[12pt,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}{13\baselineskip}
\topmargin=-5\baselineskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%        
\everymath={\displaystyle}
\begin{document}
\noindent{\bf Universit\'e de Paris 7 \hfill \framebox{\Large \bf
    \hspace{0.5cm} TP11 $(\rela/p\rela)^\times$,  applications\hspace{0.5cm}}\hfill   agreg 2010 (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(1);cas_setup(0,0,0,1,0,1e-10,10,[1,50,0,25],0,0,0); #radians,pas de cmplx, pas de  Sqrt
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% !s!<c>
% ------------------------------------------------Exercice---------------------------------------------
%!s!  
\exotitre{Primalit\'e; temps de  calculs}
\qu Etudier  les fonctions \code{nextprime} et
\code{isprime}, \verb/is_pseudoprime/. Comparer les temps d'executions
pour des nombres \`a 20 chiffres. Etudier la documentation.
% time(p:=nextprime(10^50));
% time(isprime(p));
% time(is_pseudoprime(p));
% !s!<c>
% le temps de isprime est trop long pour avoir ete utilise pour
% trouver le nombre premier avec nextprime. La doc confirme bien que
% nextprime donne un pseudopremier.
%!s!
\qusqu Etudier:\\
\verb/n:=nextprime(10^i)*nextprime(20^i);/
Essayer de factoriser $n$ pour diff\'erententes valeurs de  $i$. A partir de
quand est ce que ca ne r\'epond plus?
% i:=20;n:=nextprime(10^i)*nextprime(20^i); 
% ifactor(n);
% !s!<c>
% a partir de i=30 ca ne repond plus?
% !s!
\squ Prendre des nombres premiers de cette taille. Etudier si l'on
arrive \`a factoriser $p-1$.
% p:=nextprime(nextprime(10^30)*nextprime(20^30));
%ifactor(p-1); #ca marche souvent
\qusqu En utilisant pari, obtenir un certificat de primalit\'e  par la
m\'ethode de Lehmer (et al)  pour un nombre de cette taille. Interpr\'eter
la r\'eponse.
%pari();
%pari_isprime(p,1);
%!s!<c>
%Les grands nombres premiers apparaissant dans le certificat sont eux
%m\^eme certifi\'es, ce qui explique les crochets emboit\'es.
%!s!
\squ En cr\'eant au hasard un nombre $n$ dont vous connaissez la factorisation,
trouver un nombre pseudopremier du type $n+1$ assez grand, et tentez de le
certifier vous m\^eme. 
% !s!<c>
% On a cree n avec de petits facteurs, on arrive a le factoriser
%!s!
% !s!<m>
% i:=0;l:=[];
%  while i<1 do
%  n:=1;for j from 1 to 10 do n:=n*(1+rand(10000)) od;
%  if is_pseudoprime(n+1)>0 then p:=n+1;i++; fi;
%  od;
%!s!
\squ Comment trouver la matrice des (facteurs,multiplicit\'es) d'un
entier. Comment effectuer une grande puissance en modulaire? 
%Divn:=transpose(ifactors(p-1)[2]);
%divn:=Divn[1];
%expn:=Divn[2];
%!s!<c>
%On cherche maintenant le certificat. Pour chaque premier divisant p-1 on trouve
%un element d'ordre la puissance maximale  de ce diviseur qui divise p-1. On
%utilisera factors et powmod
%!s!
%!s!<m>
%certifs:=[];
%for i in divn do
%a:=2;
%while powermod(a,(p-1)/i,p)=1 do a:=1+rand(p-1) od;
%certifs:=[op(certifs),a];
%od;
%!s!
\squ D\'eduire de votre certificat un g\'enerateur de $(\rela/p\rela)^\times$.
% g:=1;
% for i from 1 to dim(divn) do g:=mods(g*powmod(certifs[i],(p-1)/(divn[i]^expn[i]),p),p) od;
%!s!<c>
%  seq(powmod(g,i,p),i=divisors(p-1));# NON! ne pas le faire trop de diviseurs!
%  !s!
\squ V\'erifier son ordre en utilisant pari. Cf menu aide,manuel,PARI-GP. Rappel,
pour cr\'eer un nombre modulaire sous xcas lorsque l'on est en mode maple, par
exemple le 1 de $\rela/p\rela$.

i) Soit on bascule\footnote{soit via le menu soit via la fonction maple\_mode(0)} en mode xcas et l'on fait: \verb/unp:=1%p;/ puis l'on revient
en mode maple.

% maple_mode(0); # on bascule en mode xcas et l'on cree le 1 de Z/pZ
% unp:= 1 % p; 
% maple_mode(1); #on retourne en mode maple.
ii) Soit on utilise la fonction (non document\'ee): \verb/unp:=makemod(1,p);/

% unp:=makemod(1,p); #la meme chose directement, mais c'est mal documente.
iii) Soit on utilise le logiciel pari. On charge donc pari avec \verb/pari();/,
puis on peut utiliser la syntaxe usuelle de pari: \verb/unp:=Mod(1,p);/ (Cf doc
PARI-GP dans le menu aide)
%pari(); #on charge pari une fois pour toute.
% unp:=Mod(1,p); #via pari, mais apres avoir charge pari avec: pari(); 
% !s!<c>
%On peut maitenant multiplier un entier par ce nombre modulaire pour passer
%automatiquement dans Z/pZ
%!s!
%gzp:=g*unp;
%znorder(gzp);# ou bien on pouvait faire directement:
%if znorder(Mod(g,p))==p-1 then print("ca fait bien p-1") fi;
\qu {\bf log discret:}
\squ Trouver une dizaine de nombres pseudopremiers du type $4p+1$ o\`u $p$
est un pseudopremier \`a au moins 13 chiffres. Est ce difficile de
trouver des nombres premiers tels que $p-1$ ait un grand facteur?
% p:=nextprime(10^13);i:=0;l:=[];
% !s!<m>
% while i<10 do
% if is_pseudoprime(4*p+1)>0 then l:=[op(l),4*p+1];i++; fi;
% p:=nextprime(p);
% od:l;
% !s!
\squ Chercher dans pari les intructions pour trouver un g\'en\'erateur $g$
de $(\rela/n\rela)^\times$ lorsqu'il est cyclique. Trouver un
g\'en\'erateur $g$ de  $(\rela/p\rela)^\times$ o\`u $p$ vaut
\verb/nextprime(10^13+100)/. En utilisant
\verb/pari_znlog(3,Mod(g,p))/ trouver $m$ tel que $3=g^m
[p]$. Expliquer pourquoi il a r\'eussi?
%p:=nextprime(10^13+100);
%g:=pari_znprimroot(p);
%pari_znlog(3,Mod(g,p)); #il reussit
%ifactor(p-1);
%!s!<c>
%p-1 a de petits facteurs premiers, on peut donc resoudre le probleme
%du log discret. Dans le cas suivant ca ne marche plus.
%!s!
\squ Recommencer avec un exemple du type $p=4q+1$ trouv\'e pr\'ecedemment.
% pdifficile:=l[3];
%p:=pdifficile;
% g:=pari_znprimroot(p);
%#pari_znlog(3,Mod(g,p)); #depasse la memoire max de pari
\squ Calculer la probabilit\'e  pour un \'el\'ement $x$ de $\rela/p\rela$ d'\^etre un
g\'en\'erateur de $(\rela/p\rela)^\times$ pour quelques nombres premiers grands,
puis le nombre de tirages n\'ec\'essaires pour avoir au moins 95\% de chances
d'avoir trouv\'e un g\'en\'erateur. Qu'en pensez vous (si l'on dispose d'une fa\c con
efficace de trouver l'ordre d'un \'el\'ement donn\'e)?
% !s!<c>
%Le nombre de genereurs de (Z/pZ)^x est le nombre d'inversibles dans Z/(p-1)Z,
%c'est donc phi(p-1). la Proba de trouver un generateur en piochant au hasard
%est donc de s=phi(p-1)/p. On a au moins 95 pour cent de chance d'avoir un
%generateur en n tirages ssi (1-s)^n<0.05 ssi n>ln(0.05)/ln(1-s).
% Autre maniere de commencer avec une liste vide, on utilise le symbole: NULL
%!s!
%l:=NULL;for i from 1 to 30 do p:=nextprime(rand(10^20)); l:=l,evalf(euler(p-1)/p) od;
%seq(log(0.05)/log(1-s),s=[l]);
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\squ Remarquez que  \verb/pari_znprimroot/ retourne souvent $2$, et dans le cas
contraire c'est que  $2$ n'est pas un g\'en\'erateur.
% !s!<c>
%Lorsque pari_znprimroot ne retourne pas 2, son ordre est bien different de
%p-1. On peut donc conjecturer que pari essaye successivement des petits
%entiers. Cependant il faut remarquer que le temps de znprimroot est directement
%relie au temps de factorisation de p-1. Donc pari semble avoir factorise p-1
% !s!
% l:=NULL;for i from 1 to 30 do p:=nextprime(rand(10^20)); l:=l,[pari_znprimroot(p),p-znorder(Mod(2,p))] od;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\squ Trouver des nombres premiers
$p$ de taille similaire, o\`u les temps de factorisation de $p-1$ sont tres
diff\'erents. Etudier le temps d'ex\'ecution de \code{znprimroot(p)} pour ces
valeurs de $p$, ainsi que celui de \code{znorder(Mod(2,p)}. Conjecturer comment pari 
trouve un g\'en\'erateur de $(\rela/p\rela)^\times $
%p1:=100000000003677906312417649500520066316186689905131;
%time(ifactor(p1-1));
%time(znprimroot(p1));
%time(znorder(Mod(2,p1)));
%p2:=nextprime(p1);
%time(ifactor(p2-1));
%time(znprimroot(p2));
%time(znorder(Mod(2,p2)));
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exotitre{Ecrit 2007}
% !s!<c>
% -------------------------------------EXERCICE---------------------------------------------
%!s!
\qu Choisir un nombre premier $p$ \`a 13 chiffres, tel que le probl\`eme
du log discret soit difficile modulo $p$. (Cf exercice pr\'ec\'edent)
% p:=pdifficile;
\qu Choisir un entier $b$ 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\'ecutifs. Comment obtenir les codes de chaque lettre d'un mot? (et
si l'on veut que $A$ soit repr\'esent\'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,i=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;e:=54321; igcd(e,p-1); B:=powmod(b,e,p);
% l:=asc(message);k:=[seq(rand(50),i=1..length(message))];
% C:=[seq([(b^k[i]) mod p,(l[i]*B^k[i]) mod p],i=1..length(message))];#le message crypte
\qusqu D\'ecoder le message gr\^ace \`a $e$.
%ee:=p-1-e;#c'est -e [p-1] qui nous interesse 
% !s!<c>
% L'astuce est que (B^k)=((b^e)^k) qui vaut par commutativit\'e  des la
% composition des application B:x->x^k et A:x->x^e  ((b^k)^e). 
%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[i][1],ee,p)*C[i][2],p),i=1..length(message))];
% char(decrypt);
\squ Pr\'eparer un  expos\'e de 15 minutes expliquant la m\'ethode et son
int\'er\^et. (temps pour crypter, d\'ecryper avec et sans $e$. Statitiques
sur les lettres du message crypt\'e...)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\newpage
\end{multicols}

\end{document}
