\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{ 1cm} TP9 \hspace{1cm}}\hfill   agreg 2007 (F.Han)}\\
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\code#1{{\tt #1}}
%% 
\columnsep 0.7cm
\begin{multicols}{2}
% interface(screenwidth=120);
\exo
\qusqu Convertir le r\'esultat de \linebreak\code{l:=ifactor(13*7*101);} en une liste
d'entiers. (On pourra d'abord essayer d'obtenir le \code{(7)} puis
essayer de le convertir en une liste)
% l:=ifactor(13*7*101);
% [seq(op(convert(op(l)[i],list)),i=1..nops(l))];
\squ Trouver une autre m\'ethode pour obtenir directement les facteurs
d'un entier sous forme  d'une liste.
% # ou bien avec
% ifactors(13*7*101);
\qu Comment faire calculer les puissances d'un entier modulo $N$
efficacement.
% #ASTUCE, a savoir: 2 &^1000000000000000000 mod 3;
\qu Quelle est lq diff\'erence entre \verb/factor(x^2+1) mod 2;/ et
\verb/Factor(x^2+1) mod 2;/?  
% factor(x^2+1) mod 2;# factorise dans Z puis pqsse mod 2.
% Factor(x^2+1) mod 2;# expression inerte donnee a mod qui factorise dans Z/2Z.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\def\F{{\rm I} \! {\rm F}}
\exo
\qu Factoriser le polyn\^ome $x^5+1$ dans $\F_2$ puis dans $\F_4$.
% alias(j=RootOf(x^2+x+1));
% Factor(x^5+1) mod 2;
% Factor(x^5+1,j) mod 2;
\qu On pose $p=3$. Factoriser $X^{p^n}-X$ sur $\F_{3}$ pour quelques
valeurs de $n$. Que remarquez vous sur les degr\'es de ses diviseurs par
rapport \`a $n$?
% p:=3;
% n:=2; Factor(X^(p^n)-X) mod p;
% n:=6; Factor(X^(p^n)-X) mod p;
\qu Trouver un polyn\^ome irreductible de degr\'e $6$ dans $\F_3[X]$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\exotitre{Certificat de primalit\'e; Test de non primalit\'e d'Euler.}
\qu Prendre des nombres premiers $p$ entre  $200$ et $300$. On pose
$N=2^p-1$. Tester si $N$ est premier. Regardez si maple arrive \`a le
factoriser. Comparer avec le temps de factoriser $N-1$.
% p:=107;N:=2^p-1;isprime(N);
% p:=nextprime(200);N:=2^p-1;isprime(N);
% # ifactor(N);
% ifactor(N-1);
\qu Trouver un $p$ pour que \code{isprime(N)} r\'eponde \code{true},
mais tel \code{ifactor(N-1)} soit nettement plus long. Comment
interpreter alors la r\'eponse donn\'ee.
% for i from 1 to 100 do p:=ithprime(i):N:=2^p-1:
% if isprime(N) then print(p) fi;  od:
% # on prend 521, alors
% isprime(2^521-1);
% # ifactor(2^521-2); # tres long. Donc c'est plutot une reponse
% # probabiliste qu'exacte.
\qu Prendre un $N$ de taille assez raisonnable, tel que l'on puisse
factoriser $N-1$ et certifier qu'il est premier. (On pourra d'abord
faire une proc\'edure \code{cherchex(n,N)} qui \`a $n$ fix\'e cherche au hasard
un $x$ tel que $x^n\neq 1 [ N]$ et $x^{N-1}=1 [N]$.  On prendra soin de calculer
les puissances modulo $N$ correctement)
% p:=107;N:=2^p-1;l:=ifactor(N-1);
% L:=[seq(op(convert(op(l)[i],list)),i=1..nops(l))];
% cherchex:=proc(n,N)
% f:=rand(1..N-1);
% x:=2;
% while (x&^n mod N =1) or (x&^(N-1) mod N<>1) do x:=f() od;
% x;
% end proc;
% for i from 1 to nops(L) do n:=(N-1)/L[i]; cherchex(n,N)
% od;print(N,"est certifie premier");
\qusqu  Comment faire afficher un r\'esultat entre $-N/2$ et $N/2$
% p:=101; N:=2^p-1;
% `mod`:=mods; # pour remettre entre 0 et N: `mod`:=modp;  
% a:=rand(N)();Power(a,(N-1)/2) mod N;
% # ou a&^((N-1)/2) mod N;
\squ Essayer \verb/1 in {-1,1};/ et \verb/2 in {-1,1};/. Sous maple7,
cette syntaxe ne fonctionne pas. Trouver une autre m\'ethode qui
convienne aux 2 versions.
%member(1,{-1,1});member(2,{-1,1});
\squ Prendre un autre nombre de Mersenne et certifier qu'il n'est pas
premier pour illustrer le test d'Euler. (On pourra faire une proc\'edure
\code{testeuler} qui imprime ``je ne sais pas'' au bout de 100 tirages
infructueux). Quels sont  les nombres de Mersenne $2^p-1$ pour une centaine
de nombres premiers $p$ \`a partir de  $101$ ou l'on ne sait pas?
% testeuler:=proc(N)
% f:=rand(0..N-1);
% `mod`:=mods;
% a:=f();i:=0;
% while (member(Power(a,(N-1)/2) mod N,{-1,1})) and i<100 do a:=f();i:=i+1;od ;
% if i<100 then false #print(a,"ne passe pas le test d'euler")
% else true #print("Je ne sais pas")
% fi;
% end proc;
% p:=100;for i from 1 to 100 do p:=nextprime(p);N:=2^p-1:if testeuler(N)
% then print("Je ne sais pas pour p=",p) fi;od:
% #rep 107,127,521,607

\newpage
\end{multicols}
\end{document}
