   Salut,

   Voici mon fichier.

   Comme il m'a demande au moins deux semaines de travail a plein temps en
septembre (et un peu de temps depuis), j'aimerai etre cite si l'une des
deux parties est utilisee telle quelle. J'ai moi-meme cite mes sources.

     Amicalement, Jean-Yves.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt,a4paper]{article}
\usepackage{french,amsfonts}
\addtolength{\hoffset}{-2.5cm}\addtolength{\textwidth}{5cm}
\addtolength{\voffset}{-3.5cm}\addtolength{\textheight}{7cm}
\pagestyle{empty}
\renewcommand{\thefootnote}{ }

\def\abstractname{}

\begin{document}
\begin{center}
Université Paris 7            \hfill  Année 1998/99 \\
UFR de Mathématiques        \hfill  MT 141 \\[1cm]



{\Large{\bf TP Maple n$^{\circ}$ 2}} \\[1ex] (J-Y Ducloux)
%prière de me citer en cas de réutilisation, J-Y D.

\end{center}




\begin{abstract}
Les deux thèmes de ce TP sont, d'une part la manipulation des racines de
l'unité, et
d'autre part l'étude des entiers modulo un produit de deux nombres premiers.
Vous allez dans un premier temps valider les commandes {\sc Maple} de cette
feuille
dont votre ordinateur a une copie et observer le résultat.

Ensuite, vous chercherez à comprendre les calculs faits par {\sc Maple}.
Les questions 1 à 3 auxquelles vous devez répondre sur une feuille annexe
demandent
une preuve (mathématique) de ce que les calculs de {\sc Maple} vont aboutir.
\`A la fin, s'il vous reste du temps, vous pourrez terminer le traitement
d'un des
deux thèmes en suivant les indications données dans les ``études''.
\end{abstract}







\bigskip
\begin{center}{\Large{\bf I. Expression de cos(Pi/17) par radicaux}}\end{center}
\smallskip




On va poser
\ \verb$t := Pi/17$ \
puis prouver qu'il est possible d'écrire
\ \verb$z1 := cos(t)$ \
à l'aide de nombres entiers en utilisant {\tt +}, {\tt -}, {\tt *},
{\tt /}, et l'extraction de la racine carrée de nombres réels.

Pour se rendre compte de la difficulté de ce type de problème, on admet
qu'aucune
racine $X$ de l'équation $\;X^5-6X+3=0\;$ ne s'exprime à partir des nombres
entiers en
utilisant {\tt +}, {\tt -}, {\tt *}, {\tt /}, et l'extraction de racines carrée,
cubique, ...  de nombres complexes.
Ce n'est bien sûr pas le cas pour l'équation $\;X^{34}-1=0$.


\begin{verbatim}
> restart;   cos(Pi/5);   cos(Pi/17);      #on vérifie que Maple n'a pas la
>réponse

> t := Pi/17:
  x1 := cos(3*t) + cos(5*t) + cos(7*t) + cos(11*t):
  x2 := cos(t) + cos(9*t) + cos(13*t) + cos(15*t):
  y1 := cos(3*t) + cos(5*t):
  y2 := cos(7*t) + cos(11*t):
  y3 := cos(t) + cos(13*t):
  y4 := cos(9*t) + cos(15*t):
  z1 := cos(t):
  z2 := cos(13*t):

> combine(x1+x2,trig);
> evalf(");
> combine(x1*x2+2*x1+2*x2,trig);
> combine(y1*y2,trig);
> evalf(");
> combine(y3*y4,trig);
> evalf(");
> combine(z1*z2+1/2*y1,trig);
\end{verbatim}



{\bf\underline{Question 1}}\quad
Pourquoi l'évaluation de \verb$x1+x2$ (qui intervient au total 3 fois) est-elle
correcte?


\medskip
Pour prouver la nécessité de ne pas se contenter de calculs approchés, voici une
{\it approximation} avec 7, 9, 13  chiffres après la virgule du nombre
découvert par
Ramanujan au début du siècle.

\begin{verbatim}
> restart; Ram := exp(Pi*sqrt(163)) - 262537412640768744;
  evalf(Ram,25); evalf(Ram,27); evalf(Ram,31);
\end{verbatim}


\smallskip{\bf\underline{Question 2}}\quad
Quelle expression sous forme de produit de la somme des $cos(a+kb)$ lorsque
$k$ varie
de 0 à $n-1$ (avec $\,n\in \mathbb{N}\setminus\{0\}\,$ et
$\,a,b\in\mathbb{R}$ tels que
$\;sin(b/2)\not=0\,$) permet d'obtenir les inégalités suivantes~:
{\tt x2<0<x1}, {\tt y2<0<y1}, {\tt y4<0<y3}, et {\tt z2<0<z1}?


\medskip{\bf\underline{\'Etude}}\quad
Terminer le calcul de $\,cos(\pi/17)\,$.
Pour cela, on utilisera la fonction ``\verb$solve$'' de {\sc Maple}.


\medskip
La formule pour $\,cos(\pi/17)\,$ qui vient d'être obtenue permet de
construire à la
règle et au compas un polygône régulier à 17 (ou 34) cotés. Ce résultat a
été obtenu
par Gauss en 1796, à 18 ans.
Par la suite, il a affirmé avoir la preuve (et il ne fait aucun doute qu'il
l'ai eue)
du résultat suivant~: les polygônes réguliers dont la construction à la
règle et au compas est possible sont ceux dont le nombre de cotés est de la
forme
$\; n=2^k n_1...n_l\;$, où $\,k\in\Bbb N\,$ et les $\,n_i\in\Bbb N\,$ sont
premiers
distincts de la forme  $\;n_i = 2^{(2^m)} + 1\;$ avec $\,m\in\Bbb N$.
Peu de nombres premiers de la forme  $\;2^{(2^m)} + 1\;$ sont connus.
Celui qui suit 17 est 257.


\medskip
{\bf Bibliographie}~:

Le chapitre 17 de la deuxième édition du livre ``Galois Theory'' de Ian Stewart.
Voir aussi la page 39 du dossier hors série de janvier 1994 de la revue
``Pour la
science''.







\bigskip
\begin{center}{\Large{\bf II. Cryptographie à clef publique
(systèmeRSA)}}\end{center}
\smallskip




   On commence par construire un nombre $n$ d'une centaine de chiffres.
Il est produit de deux nombres premiers $p$ et $q$ qui seront tenus secrets.
On choisit aussi un nombre $\,e \!\geq\! 2\,$ qui est premier avec $(p-1)(q-1)$.

La clef $(n,e)$ qui va permettre à mes correspondants de m'envoyer des
messages codés
est dans l'annuaire à coté de mon nom.
La clef $d$ du décodage se calculera à partir de $p$ et $q$.

Il faut savoir que la transmission de messages cryptés non déclarés a été
longtemps
\underline{\it interdite} en France. J'ignore ce qu'il en est actuellement.


\begin{verbatim}
> restart; p := nextprime(rand(10^49..10^50)()):    #on choisit p et q avec
>50 chiffres
  q := nextprime(rand(10^49..10^50)()):  n := p*q;   #n est peu aléatoire!
(cf "rand")
> isprime(n);                                   #normalement "ifactor(n)"
>n'aboutit pas
> e := nextprime(rand(10^3..10^4)());     #on se donne e premier avec (p-1)(q-1)
\end{verbatim}


Ensuite, on crypte une ligne de message (d'au plus 69  caractères) traduite par
$m \in \Bbb N$ avec $m < n$, et l'envoie sous la forme d'une ligne de
message crypté
traduite par $c =\verb$code$ \in \Bbb N$. Puis on décrypte.

\begin{verbatim}
> m := 4817021;
> code := m&^e mod n;                #pourquoi pas "m^e mod n"?
> x := 'x': d := op(1,op(Roots(e*x-1) mod (p-1)*(q-1)));
> decode := c&^d mod n;
   #normalement "Roots(x^e - c) mod n" n'aboutit pas
\end{verbatim}


{\bf\underline{Question 3}}\quad
Prouver que la méthode utilisée permet de décoder tous les messages.


\medskip{\bf\underline{\'Etude}}\quad
Réaliser le codage et le décodage automatique d'un texte d'une ligne d'au
plus 69
caractères, écrit avec l'alphabet usuel de 26 lettres auquel on adjoint le
symbole
``\verb$_$'' pour représenter un espace. On utilisera les fonctions
``\verb$convert[base]$'' et ``\verb$sum$'' de {\sc Maple}, et s'inspirera
des exemples
suivants~:
\smallskip

\noindent
$\left[ \vcenter{\noindent
$\scriptstyle >$ \verb$m27 := op(subs({ 'a'=1,'e'=5,'i'=9,'s'=19},$ \\
$~~~$ \verb$                      [seq( substring(essai,i) ,
i=1..length(essai))]));$
\\
\centerline{$m27 := 5, 19, 19, 1, 9$}
}\right.$

\noindent
$\left[ \vcenter{\noindent
$\scriptstyle >$ \verb$s := [m27]:    nops(s);    s[3];$ \\
\centerline{$5$} \\
\centerline{$19$} \\
}\right.$

\noindent
$\left[ \vcenter{\noindent
$\scriptstyle >$
\verb$alpha := proc() subs( { 1='a',5='e',9='i',19='s'},[args] ): end:$ \\
$~~~$ \verb$cat(op(alpha(m27)));$ \\
\centerline{$essai$}
}\right.$



\medskip
{\bf Bibliographie}~:

Ce thème a été préparé à partir de l'encart page 90 du numéro de septembre
1998 de la
revue ``Pour la science''.
On peut aussi regarder l'encart page 764 du numéro spécial de la revue ``La
recherche'' de juillet/août 1995. La cryptographie à clef publique a été
inventée en
1976 par W. Diffie et M. Hellman. Le système RSA est dû à R. Rivest, A.
Shamir et L.
Adleman en 1978.





\end{document}



