Cours numéro 6 :

arithmétique et cryptographie

1 Introduction
Si l’on m’avait demandé quand j’étais jeune chercheur, dans les années
1970, à quoi servaient les nombres premiers dans la vie courante, j’aurais
répondu sans hésiter, à rien, et j’aurais peut-être ajouté comme un de mes
vieux collègues, un peu bougon1 , qu’en tout cas ils ne servaient pas à faire
la bombe atomique. En fait, j’aurais dit une bêtise, puisque les nombres
premiers, avec le code RSA, jouent maintenant un rôle de premier plan dans
tous les secteurs de la communication, de la finance, etc. et que parmi leurs
principaux utilisateurs se trouvent justement ... les militaires.

2 La cryptographie
La cryptographie (du grec crypto, caché et graphie, écrire) est la science
des codes secrets. Elle remonte à l’antiquité et Jules César l’a employée pour
coder ses messages. Il utilisait le système le plus simple, celui des alphabets
décalés d’un ou plusieurs crans (où l’on remplace, par exemple, A par B, B
par C, etc). Ainsi peut-on penser qu’il envoya au sénat, après sa victoire sur
Pharnace à la bataille de Zela, le message suivant : TCLG TGBG TGAG.
Bien entendu des méthodes beaucoup plus sophistiquées ont été inventées
depuis. Le plus souvent ces méthodes utilisent le principe suivant. On code
les lettres de l’alphabet de A à Z par les nombres2 de 1 à 26. On traduit
le message en chiffres. Par exemple si le message est A L’AIDE il devient
1 12 1 9 4 5. Ensuite on permute les nombres de 1 à 26 selon une certaine
règle. On obtient par exemple ici 25 14 25 17 22 21 avec une règle très simple
que je vous laisse deviner3 . On retraduit alors le message en lettres et on
a YNYQVU. On notera que dans ce message on voit tout de suite qu’une
1
Un indice : il a aussi écrit un cours d’algèbre.
2
Dans la réalité on utilise plus de symboles, par exemple ceux du code ASCII.
3
Une méthode très simple de codage consiste à transformer l’entier z variant entre 1
et 26 en az + b avec a, b entiers et a premier à 26, et à réduire ce nombre modulo 26, voir
ci-dessous.

1
lettre intervient deux fois (le Y , traduction de A). Le défaut de ce genre
de méthodes est dans cette remarque : elles ne résistent pas au décryptage
par analyse de fréquences qui consiste à identifier quelles sont les lettres qui
interviennent le plus.
C’est d’ailleurs ainsi que Marie Stuart, princesse écossaise, reine de France
(1559-1560) puis d’Ecosse, a péri. En effet, elle était l’ennemie de la reine
d’Angleterre Elisabeth première et elle fut capturée par elle en 1568. En 1586
elle participe de sa prison à un complot contre Elisabeth et communique avec
ses partisans au moyen de messages codés. Mais ceux-ci sont interceptés par
les anglais et son code est décrypté par Thomas Phelippes. Marie est accusée
de complot, condamnée et décapitée en 1587.
Ce procédé est expliqué dans la nouvelle d’Edgar Poë : Le scarabée d’or.
Il s’agit de déchiffrer un grimoire écrit par le capitaine Kidd, qui indique où
se trouve le trésor caché par les pirates. Voici ce message :
53‡‡+305))6* ;4826)4‡4‡) ;806* ;48+8 960))85 ;1‡( ; :+*8+83(88)5*+
;46( ;88*96 * ? ;8)*‡( ;485) ;5*+2 :*‡( ;4956*2(5*-4)8 98* ;4069285) ;)6
+8)4‡‡ ;1(‡9 ;48081 ;8 :8‡ 1 ;48+85 ;4)485+528806*81(‡9 ;48 ;(88 ;4 (‡ ?
34 ;48)4‡ ;161 ; :188 ;‡ ? ;
Le héros de l’histoire, William Legrand, après avoir déterminé que le
message est en anglais, part de la remarque que, dans cette langue, la lettre
la plus fréquente est le E, ce qui lui donne E = 8. Il continue ainsi de proche
en proche (notamment en identifiant la suite de caractères ; 48 comme l’article
THE).
Par cette méthode, vous devez réussir à déchiffrer le message ci-dessous4 :
SALCFCFVHLCNEANVHHPLGNZIPUUANAKNRNHHLBNCFVH
NYOANEGLYHKNZKVSOANHUNARNGNHZLHHNVAHGNZFGNH
HNZANOHUALYZLPHKNHNHMPFYHYFYOMKVHTVLSPNYHN
ONYPAUNKPZPOLOPFYH
en sachant qu’en français les lettres statistiquement les plus fréquentes sont,
dans l’ordre, E, puis S et A, puis R, I, N et T, puis U, puis O et L, etc.
Bien entendu on peut parfois avoir quelques surprises comme avec le texte
suivant :
Un voisin compatissant l’accompagna à la consultation à l’hôpital Cochin.
Il donna son nom, son rang d’immatriculation à l’Association du travail.
On l’invita à subir auscultation, palpation, puis radio. Il fut d’accord. On
l’informa : souffrait–il ? Plus ou moins, dit–il. Qu’avait–il ? Il n’arrivait pas
4
Codage : ax + b = 7x + 5 modulo 26. On trouve que E devient N et S devient H.
Cela ne suffit pas pour trouver a, b car le déterminant des deux équations 5a + b = 14 et
19a + b = 8 est 12 qui n’est pas inversible.

2
à dormir ? Avait–il pris un sirop ? Un cordial ? Oui, il avait, mais ça n’avait
pas agi. Avait–il parfois mal à l’iris ? Plutôt pas. Au palais ? Ca pouvait ;
Au front ? Oui. Aux conduits auditifs ? Non, mais il y avait, la nuit, un
bourdon qui bourdonnait. On voulut savoir : un bourdon ou un faux-bourdon ?
Il l’ignorait.
Il fut bon pour l’oto-rhino, un gars jovial, au poil ras, aux longs favoris
roux, portant lorgnons, papillon gris à pois blancs, fumant un cigarillo qui
puait l’alcool. L’oto-rhino prit son pouls, l’ausculta, introduisit un miroir
rond sous son palais, tripota son pavillon, farfouilla son tympan, malaxa son
larynx, son naso–pharynx, son sinus droit, sa cloison. L’oto-rhino faisait du
bon travail, mais il sifflotait durant l’auscultation ; ça finit par aigrir Anton.
(Il s’agit d’un extrait du livre de 319 pages de Georges Perec (1969),
intitulé La disparition et qui ne comporte pas la lettre E.)

3 Le code RSA
3.1 Le principe
La méthode RSA dont nous allons parler a été inventée en 1978 par
Rivest, Shamir et Adleman (RSA) et repose sur les nombres premiers. La
problématique de cette méthode est la suivante.
Imaginons un espion E (Ernesto), loin de son pays et de son chef C (Car-
los). Il doit transmettre des messages secrets à C. Pour cela, il a besoin d’une
clé pour coder ses messages. Cette clé doit lui être transmise par son chef. Le
problème, de nos jours, avec Internet et tous les satellites qui nous tournent
autour, c’est qu’on n’est pas sûr du tout que les ennemis n’écoutent pas les
messages transmis. Avec la plupart des systèmes de codage, si l’on connaı̂t la
clé de codage, on sait aussi décoder les messages. Par exemple, imaginons que
la clé soit l’opération qui à une lettre, représentée par un nombre x modulo
26, associe 11x − 7 (toujours modulo 26), ce qui associe par exemple à la
lettre E la lettre V . On calcule alors facilement l’opération inverse5 , ce qui
permet de décoder les messages.
L’intérêt du code RSA, au contraire, c’est qu’il est à sens unique : la clé
de codage n’est pas une clé de décodage ! Voici le principe de cette méthode.
Le chef C calcule deux grands nombres premiers p et q (disons de l’ordre
de 200 chiffres), il calcule ensuite le produit pq (cela ne représente qu’une
fraction de seconde pour une machine). Il choisit aussi un nombre e premier
avec p − 1 et q − 1 (il y en a beaucoup, par exemple un nombre premier qui
ne divise ni p − 1 ni q − 1). Il transmet à E la clé de codage, qui est constituée
5
C’est x 7→ −7x + 3, voir ci-dessous.

3
du nombre pq et du nombre e (mais il garde jalousement secrets les deux
nombres p et q). La clé est publique : peu importe si l’ennemi l’intercepte.
Pour coder le message, E n’a besoin que pq et de e, en revanche, pour le
décoder, le chef C a besoin des deux nombres p et q. Le principe qui fonde le
code RSA c’est qu’il est beaucoup plus facile de fabriquer de grands nombres
premiers p et q (et de calculer pq) que de faire l’opération inverse qui consiste
à décomposer le nombre pq en le produit de ses facteurs premiers.
Voici précisément la méthode de codage. Le message est un nombre a < pq
et premier6 avec p et q. Pour le coder, E calcule ae modulo pq (le reste r de
ae dans la division par pq). Là encore, une machine fait cela instantanément,
voir ci-dessous. C’est ce nombre r qu’il envoie à son chef.
Comment faire pour retrouver a à partir de r ? Nous l’expliquons en détail
au paragraphe suivant. L’idée est la suivante : comme e est premier avec
pq, le théorème de Bézout montre qu’il existe un nombre d tel que de ≡ 1
(mod (p−1)(q −1)). On montre que grâce à ce d on peut calculer a en faisant
l’opération à l’envers : a = rd (mod pq). Il suffit donc de calculer d. Quand
on connaı̂t (p − 1)(q − 1), trouver d est facile (c’est l’algorithme d’Euclide).
Mais voilà : on a (p − 1)(q − 1) = pq − p − q + 1 et pour connaı̂tre ce nombre
il nous faut p + q, donc p et q et ça, on ne sait pas faire et c’est ce qui assure
la sécurité du code RSA.

3.2 Quelques résultats arithmétiques

Rappelons d’abord le petit théorème de Fermat :
3.1 Théorème. Soient p un nombre premier et a ∈ Z. Alors p divise ap − a
donc on a ap ≡ a modulo p. Si de plus a est premier avec p, on a ap−1 ≡ 1
(mod p).
On a un corollaire de ce théorème :
3.2 Corollaire. Soient p et q deux nombres premiers distincts et soit a
premier avec pq. Alors on a a(p−1)(q−1) ≡ 1 (mod pq).
Démonstration. Il suffit de montrer que la congruence est vraie modulo p et
modulo q. Pour cela on note que, comme ap−1 est congru à 1 modulo p, on a
aussi a(p−1)(q−1) = (ap−1 )q−1 ≡ 1q−1 = 1 (mod p). On procède de même pour
q.
Le résultat suivant concerne encore les congruences (et c’est aussi la re-
cette pour résoudre des équations du genre ax ≡ b (mod s)) :
6
Pour être sûr de réaliser cela on prendra des messages plus petits que p et q. Par
exemple si pq a 200 chiffres, on prendra des messages de moins de 100 chiffres. Ce seront
des messages élémentaires, il en faudra sans doute plusieurs pour faire un message réel.

4
3.3 Proposition. Soit s un entier > 0 et soit e un entier > 0 premier avec
s. Alors il existe un entier d > 0 tel que de ≡ 1 (mod s).

Démonstration. On applique le théorème de Bézout à s et e : il existe des

entiers λ et µ avec λs + µe = 1. Si µ est > 0 il suffit de poser d = µ. Sinon,
on remplace µ par µ + sk et λ par λ − ek avec k assez grand.
Enfin, le dernier résultat est la base de la méthode RSA :

3.4 Proposition. Soient p et q deux nombres premiers distincts et soit a > 0

premier avec pq. Soit e un entier > 0 premier avec (p −1)(q −1) et soit d > 0
tel que de soit congru à 1 modulo (p − 1)(q − 1) (un tel entier existe par 5.3).
Alors, on a ade ≡ a (mod pq).

Démonstration. On a de = 1 + m(p − 1)(q − 1), avec m > 0, donc, en vertu

de 3.2 :
ade = a × a(p−1)(q−1)m ≡ a × 1m = a (mod pq).

3.3 Méthodes de calcul : puissances

3.3.1 Un exemple
Considérons l’exemple suivant : n = pq = 11639, e = 3361 et supposons
que le message a est égal à 2511. Il s’agit de calculer ae modulo pq.

3.3.2 Avec la calculatrice, sans programme

Attention, on ne peut pas calculer directement 25113361 sinon la machine
répond ∞ car on a dépassé sa capacité. Le principe est de réduire à chaque pas
modulo n. Une méthode élémentaire, mais déjà efficace, est la suivante. On
calcule mod(251110 , 11639) (le reste de la puissance dans la division par n).
On trouve 5868. On recommence en calculant 586810 modulo n, soit 9609, puis
960910 modulo n, soit 2083. Ce nombre n’est autre que 25111000 modulo n. On
élève ce nombre au cube, ce qui donne 1146 (on a ainsi la puissance 3000), on
trouve de même la puissance 300 : 11138 et on calcule directement 251161 ≡
2990 (mod n). En multipliant les trois on a 25113361 ≡ 9404 (mod n).

3.3.3 Avec la calculatrice, la voie des puissances de 2

C’est une méthode plus astucieuse qui va donner un algorithme très ra-
pide. Elle combine deux types d’opérations simples :
1) l’élévation au carré,
2) la multiplication par a = 2511.

5
 La méthode est la suivante : on part de e, si e est pair on le divise
par 2, sinon on lui retranche 1, il est alors pair, on le divise par 2 et on
recommence avec le quotient. On finit par aboutir à 1. (Si on écrit e en base
2, les opérations consistent à supprimer le dernier chiffre si c’est un 0 ou à le
changer en 0 si c’est un 1.)
Avec e = 3361 on obtient successivement les nombres 3360, 1680, 840,
420, 210, 105, 104, 52, 26, 13, 12, 6, 3, 2, 1, autrement dit, on a écrit, en base
2:
3361 = 1010010001000001.
On obtient alors le résultat en partant de la gauche de ce nombre et en
multipliant par 2511 chaque fois qu’on rencontre un 1 et en élevant au carré
pour chaque 0 (et bien entendu en réduisant modulo n à chaque pas). Voici les
intermédiaires : 8422, 11218, 2656, 1102, 8679, 9072, 1815, 388, 8231, 10381,
11299, 10849, 7233, 10623, et enfin 9404. À faire à la main c’est pénible, mais
on va écrire un programme qui fait le même travail.

3.3.4 Programmes
Voici deux programmes (en fait, ce sont des fonctions au sens de la TI
Voyage 200) pour faire automatiquement ces calculs de puissance. En voici
deux, le premier est plus simple7 , mais le second bien plus rapide (une seconde
au lieu de cinquante-cinq pour le calcul ci-dessus). Chacun de ces programmes
calcule la puissance r-ième de a modulo p. Le premier consiste à multiplier
ak par a et à réduire modulo p à chaque pas :
power(a,r,p)
Func
Local k,z
1 → z
For k,1,r
mod(a*z,p) → z
EndFor
Return z
EndFunc

Le second programme utilise les puissances de 2, comme expliqué plus

haut, pour grimper plus vite :
powerv(a,r,p)
Func
Local z
7
Et facile à retrouver.

6
 1 → z
While r > 0
If entPrec(r/2)= r/2 Then
r/2 → r
mod(aˆ2,p) → a
Else
(r-1)/2 → r
mod(z*a,p) → z
mod(aˆ2,p) → a
EndIf
EndWhile
Return z
EndFunc

3.4 Méthodes de calcul : les coefficients de Bézout

Reprenons notre exemple : n = pq = 11639, e = 3361 et a = 2511. On a
trouvé ae ≡ 9404 (mod n).
Pour inverser le processus, il y a besoin de connaı̂tre (p − 1)(q − 1), donc
p et q. Ici, ce n’est pas trop compliqué : on a p = 103 et q = 113, d’où
(p − 1)(q − 1) = 11424 = 25 × 3 × 7 × 17. Comme e est premier, il est bien
premier avec ce nombre. Il s’agit maintenant de trouver d tel que de ≡ 1
(mod 11424). Pour cela, on utilise l’algorithme d’Euclide pour trouver les
coefficients de Bézout.

3.4.1 L’algorithme d’Euclide

On considère a, b ∈ N avec b 6= 0. On pose a = r0 , b = r1 . On effectue la
division euclidienne de a par b : a = bq + r avec 0 ≤ r < b. On pose q = q1 ,
r = r2 . On a donc r0 = r1 q1 + r2 avec 0 ≤ r2 < r1 et d = pgcd (a, b) =
pgcd (r0 , r1 ) = pgcd (r1 , r2 ).
On construit ainsi par récurrence des entiers r0 , r1 , · · · , rk , rk+1 et q1 , · · · , qk
avec rk−1 = qk rk + rk+1 , 0 ≤ rk+1 < rk et d = pgcd (rk , rk+1 ). Si on a rk+1 = 0
on a d = rk et on s’arrête, sinon on continue l’algorithme en divisant rk par
rk+1 .
Comme on a 0 ≤ rk+1 < rk < · · · < r1 on voit que l’on obtient
nécessairement un reste nul au bout d’au plus r1 opérations. Si on désigne par
rn le dernier reste non nul on a donc rn−1 = qn rn d’où, d = pgcd (rn−1 , rn ) =
rn .

7
3.4.2 Le théorème de Bézout
Pour montrer Bézout, on utilise l’algorithme d’Euclide. On va montrer,
par récurrence sur k que, pour tout k avec 0 ≤ k ≤ n, il existe des entiers
uk , vk ∈ Z vérifiant rk = uk a + vk b.
L’assertion est vraie pour k = 0 puisqu’on a r0 = a = 1 × a + 0 × b et
pour k = 1 puisqu’on a r1 = b = 0 × a + 1 × b. Supposons l’assertion prouvée
pour tout entier ≤ k, avec k fixé vérifiant 1 ≤ k < n, et montrons la pour
k + 1. On a rk+1 = rk−1 − qk rk = uk−1 a + vk−1 b − qk (uk a + vk b) d’où la relation
cherchée en posant uk+1 = uk−1 − qk uk et vk+1 = vk−1 − qk vk .
Si on applique l’assertion au cas k = n, comme on a rn = d = pgcd (a, b),
on obtient bien la relation de Bézout cherchée.
Pour écrire la récurrence sur les
 coefficientsuk , vk le mieux est d’introduire
uk−1 vk−1
la matrice mk suivante : mk = car la relation de récurrence
uk vk  
0 1
s’écrit alors mk+1 = pk mk où pk est la matrice .
1 −qk

3.4.3 Le programme sur Voyage

euclide(a,b)
Prgm
EffES
Local m,q,r
Identité(2) → m
While b > 0
mod(a,b) → r
(a-r)/b → q
b → a : r → b : [ [0, 1] [1, −q] ]∗m → m
EndWhile
Disp "pgcd", a Disp "u", m[1,1] Disp "v", m[1,2]
EndPrgm

3.4.4 Application
Si l’on applique euclide(11424, 3361) on trouve u = −198 et v = 673.
Ce dernier nombre est le d cherché. On vérifie qu’on a bien 9404673 ≡ 2511
(mod n).

8
3.5 Trouver de grands nombres premiers
On sait depuis Euclide qu’il y a une infinité de nombres premiers mais il
n’est pas si facile d’en donner explicitement de très grands. Pierre de Fermat
(1601-1665) avait cru trouver une formule donnant à coup sûr des nombres
n
premiers. Il prétendait que, pour tout entier n, le nombre8 Fn = 22 + 1 était
premier. C’est effectivement le cas pour n = 0, 1, 2, 3, 4 qui correspondent
respectivement aux nombres premiers 3, 5, 17, 257, 65537, mais ce n’est pas
vrai pour F5 comme l’a montré Euler9 .
(On peut faire le calcul à la main jusqu’à 257. Pour voir que 65537 est
premier, mais que 232 + 1, 264 + 1 et 2128 + 1 ne le sont pas on peut utiliser
la fonction EstPrem de la calculatrice TI Voyage 200 qui répond presque
instantanément. (Même pour 2512 + 1 elle donne une réponse négative en
une minute environ.) La calculatrice factorise facilement 232 + 1 et 264 + 1
(mais cela prend plus de temps).

232 + 1 = 641 × 6700417

Ensuite, on a :

264 + 1 = 274177 × 67280421310721

En revanche, pour le suivant, elle ne donne rien en un quart d’heure10 , mais
le logiciel Pari le donne sans peine :

2128 + 1 = 59649589127497217 × 5704689200685129054721.)

On notera qu’à l’heure actuelle on ne sait pas exactement lesquels parmi les
Fn sont premiers ou non. La réponse est seulement connue pour un nombre
fini de n et, sauf pour les 5 premiers, tous les Fn en question sont composés.
Cet exemple montre déjà deux choses, d’abord qu’un grand mathématicien
peut dire des bêtises, et ensuite qu’il y a des questions, somme toute assez
simples, pour lesquelles on n’a pas de réponse. J’y reviens plus loin.
Il y a donc des records du plus grand nombre premier connu qui sont
détenus par d’énormes ordinateurs11 (en général il s’agit de certains nombres
8
Seuls les 2r + 1 où r est une puissance de 2 ont une chance d’être premiers à cause de
la formule am + 1 = (a + 1)(am−1 − am−2 + am−3 − · · · − a + 1) lorsque m est impair.
9
On montre que 641 divise 232 + 1. Cela repose sur les égalités 641 = 625 + 16 = 54 + 24
et 641 = 640 + 1 = 27 × 5 + 1. Modulo 641 on a donc 228 × 54 = 1 et comme 54 = −24 ,
on a bien 232 = −1.
10
On constate sur cet exemple que la primalité est plus facile que la factorisation !
11
Ce n’est pas seulement la puissance des ordinateurs qui est en jeu, mais surtout la
qualité des algorithmes qu’ils utilisent (donc des mathématiques qui sont derrière).

9
de Mersenne (1588-1648) : Mn = 2n − 1). Le plus ancien record est celui de
Cataldi en 1588 avec M19 = 524287. Il y eut ensuite Lucas (1876) avec M127
qui a 39 chiffres. Le record, en 1999, était le nombre de Mersenne M6972593 qui
a tout de même plus de 2 millions de chiffres ! Je ne vais pas l’écrire12 , mais
je peux tout de même dire qu’il commence par 437075 et finit par 193791. Je
vous laisse montrer cela à titre d’exercice (pas si facile).
En 2008, le record est M43112609 qui a 12 millions de chiffres.

3.6 Factoriser des grands nombres ?

Ce qu’il faut comprendre, c’est que les ordres de grandeur des nombres
premiers que l’on sait exhiber, d’une part, et des nombres que l’on sait fac-
toriser, d’autre part, ne sont pas du tout les mêmes, comme on l’a déjà senti
à propos des nombres de Fermat. Pendant longtemps, factoriser un nombre
de l’ordre d’un milliard était considéré comme à peu près impossible. Ainsi
Mersenne, en 1643, avait donné à Fermat, comme un défi, de factoriser le
nombre13 100895598169 et le même défi avait été présenté comme impossible
par Stanley Jevons en 1874 avec le nombre 8616460799. Pourtant, aujour-
d’hui, une calculatrice un peu perfectionnée factorise ces deux nombres sans
difficulté.
Cependant, le record absolu de factorisation (en février 2010) est bien
loin de celui de primalité, c’est un nombre n de 232 chiffres, produit de deux
nombres p et q de 116 chiffres, et encore a-t-il fallu pour cela faire travailler
plusieurs centaines d’ordinateurs en parallèle pendant 2 ans sur un algorithme
très complexe, ce qui représente environ 1500 années de temps de calcul pour
une machine seule.
Voilà ces nombres :
1230186684530117755130494958384962720772853569 5953347921973224
521517264005072636575187452021997864693899564749427740638459251
925573263034537315482685079170261221429134616704292143116022212
40479274737794080665351419597459856902143413
= 3347807169895689878604416984821269081770479498371376856891
2431388982883793878002287614711652531743087737814467999489
×
367460436667995904282446337996279526322791581643430876426760
322838157396665112792 33373417143396810270092798736308917
12
Il y faudrait un livre de 500 pages !
13
Fermat avait répondu au défi, et semble-t-il très rapidement. On ignore comment il
a fait. On trouvera en annexe une hypothèse que je soumets au lecteur, sans la moindre
garantie.

10
 On notera tout de même qu’il y a seulement 30 ans, on estimait qu’il
faudrait 50 milliards d’années pour factoriser un nombre de 150 chiffres.
Les progrès accomplis par les mathématiciens et les ordinateurs sont donc
considérables. Bien entendu, cela ne remet pas en cause la fiabilité du code
RSA : si on sait factoriser un nombre n = pq de 250 chiffres il suffit de choisir
des nombres p et q plus grands. On a vu qu’il y a de la marge puisqu’on sait
expliciter des nombres premiers avec des millions de chiffres. Les banques
travaillent déjà avec des clés n de l’ordre de 300 chiffres et les militaires avec
des clés de 600 chiffres.
Et si un mathématicien améliorait fondamentalement les algorithmes de
factorisation et leur permettait de rattraper les tests de primalité ? Alors,
pour un temps au moins, il ne serait pas loin d’être le maı̂tre du monde14 !
Si vous pensez détenir une méthode, voici un nombre à factoriser, qui
vous rapportera la modique somme de 200 000 dollars :
251959084756578934940271832400483985714292821262040320277771378
36043662020707595556264018525880784406918290641249515082189298
5591491761845028084891200728449926873928072877767359714183472
70261896375014971824691165077613379859095700097330459748808428
401797429100642458691817195118746121515172654632282216869987
5491824224336372590851418654620435767984233871847744479207399
342365848238242811981638150106748104516603773060562016196762
56133844143603833904414952634432190114657544454178424020924616
515723350778707749817125772467962926386356373289912154831438167
899885040445364023527381951378636564391212010397122822120720357

3.7 Combien de nombres premiers dans une dizaine ?

Ce paragraphe a pour but de montrer combien il est difficile de savoir
d’avance quelle va être la difficulté d’une question.
Si on regarde combien il y a de nombres premiers dans une dizaine, on
peut éliminer les multiples de 2 et ceux de 5. Il reste donc à regarder les
nombres se terminant par 1, 3, 7, 9. Il se peut qu’ils soient tous premiers,
c’est le cas de 11, 13, 17, 19, mais c’est rare. Si l’on cherche ensuite, cela
n’arrive plus jusqu’à 100 (sont non premiers : 21, 33, 49, 51, 63, 77, 81, 91).
En revanche, 101, 103, 107 et 109 sont tous premiers (il suffit de voir qu’ils
ne sont pas multiples de 3 ni de 7). La question est donc : peut-on trouver
une infinité de dizaines riches contenant 4 nombres premiers ? La calculatrice
(et l’ordinateur) permettent d’explorer le problème (jusqu’à 10000 il y a 11
14
N’ayez pas trop d’espoir tout de même. On pense qu’il a vraiment une raison profonde
qui fait que la factorisation est beaucoup plus difficile que la primalité.

11
dizaines riches), mais pas de le résoudre et, à l’heure actuelle, on ne sait pas
s’il y a une infinité de telles dizaines. Pire, on ne sait même pas s’il y a une
infinité de nombres premiers jumeaux (c’est-à-dire avec 2 d’écart comme 11
et 13, ou 59 et 61).
Ce dernier problème date des Grecs, il est très facile à exprimer, mais
très difficile, puisque personne n’a su le résoudre encore. Bien entendu, ce
problème a été exploré avec l’ordinateur (jusqu’à 1015 on a trouvé environ
1177 milliards de paires de jumeaux), mais cela ne permet pas de répondre
à la question : les capacités des ordinateurs, même immenses, sont finies.
À propos de la répartition des nombres premiers, si l’on regarde le début
des tables on peut avoir l’impression qu’il y a des nombres premiers dans
toutes les dizaines. Eh bien, ce n’est pas vrai et il n’y a pas besoin d’aller
chercher très loin (il n’y en a pas entre 200 et 210). En fait, même si on prend
un nombre même très grand (disons par exemple 1000, voire un milliard),
on peut toujours trouver 1000 nombres (ou un milliard) de suite sans aucun
nombre premier. Cette affirmation semble ambitieuse ? Elle est pourtant bien
facile à prouver si l’on pense aux factorielles.
Sur ces deux exemples, on voit combien il peut être délicat de prévoir,
face à un problème de mathématiques inconnu, quelle va être sa difficulté.

4 Annexe 0, codage par application affine

4.1 Le codage
4.1 Proposition. Soient a, b deux entiers compris entre 0 et 25. On suppose
a premier à 26 (c’est-à-dire impair et différent de 13). Alors l’application
Φ : Z/26Z → Z/26Z qui à x associe ax + b (modulo 26) est bijective.

Démonstration. Il suffit de montrer qu’elle est injective. Si on a ax + b =

ay + b, cela signifie a(x − y) ≡ 0 (mod 26), donc a(x − y) multiple de 26
et comme a est premier avec 26, cela donne x ≡ y (mod 26) en vertu du
théorème de Gauss.

4.2 Le décodage
Le décodage se fait en utilisant Bézout. On a y et on cherche x vérifiant
y = ax + b. Si l’on connaı̂t l’inverse de a modulo 26 on a x = a−1 (y − b).
Pour cela on écrit l’égalité de Bézout : λa + 26µ = 1 et λ est un inverse de a.

4.2 Exemple. Si l’on pose Φ(x) = 11x − 7 = 11x + 19, on peut calculer
l’inverse de 11 par la méthode artisanale : on se récite les multiples de 26

12
jusqu’à ce qu’on voie un multiple de 11 qui le jouxte : 26, 52, 78, stop. On a
donc 3 × 26 − 7 × 11 = 1, de sorte que l’inverse de 11 est −7 (ou 19 si l’on
préfère) et on a alors Φ−1 (y) = −7(y + 7) = −7y + 3.

5 Annexe 1, Euler et les nombres de Fermat

On a vu, grâce à la calculatrice, que 641 divise F5 = 232 + 1. La ques-
tion est de savoir comment on peut trouver ce facteur et comment montrer
directement qu’il divise F5 .

5.1 Montrer que 641 divise F5

On pose p = 641 (on vérifie que c’est bien un nombre premier). On note
les deux formules : 641 = 625 + 16 = 54 + 24 et 641 = 640 + 1 = 5 × 27 + 1. On
calcule 232 modulo p. On a 5 × 27 ≡ −1 (mod p). En élevant cette relation
à la puissance 4 on a 54 × 228 ≡ 1 (mod p). Mais, on a 54 ≡ −24 (mod p) et
donc 232 ≡ −1 (mod p). Cela signifie exactement que p divise 232 + 1.

5.2 D’où sort le 641 ?

On suppose que F5 admet un facteur premier p et on travaille dans le
groupe multiplicatif G = (Z/pZ)∗ . Dans ce groupe on a donc 232 = −1, donc
264 = 1. On voit que 2 est un élément d’ordre 64 de G. Comme l’ordre d’un
élément divise l’ordre du groupe, c’est que 64 divise p − 1. Cela signifie que
p est congru à 1 modulo15 64. On examine les nombres premiers possibles :
193, 257, 449, 577, 641, le cinquième est le bon16 .

5.3 Éliminer les autres possibles

Pour p = 257 c’est évident car on a 28 ≡ −1 (mod p) donc 216 ≡ 1 et
32
2 ≡ 1.
Pour 193 on peut par exemple raisonner ainsi. On a 192 = 3 × 64 et
donc 3 × 26 ≡ −1 (mod p). On en déduit 34 × 224 ≡ 1 et, si l’on suppose
232 = 224 × 28 ≡ −1 on trouve 28 + 34 ≡ 0 (mod p), ce qui est clairement
faux.
15
En fait, quand on est plus instruit, on sait même que p est congru à 1 modulo 128.
En effet, comme p est congru à 1 modulo 8, 2 est un carré modulo p, 2 = a2 et on a donc
a64 = −1, donc a est d’ordre 128 dans G.
16
Il y a seulement à éliminer 257 si l’on a utilisé la ruse et c’est évident car c’est lui-même
un nombre de Fermat.

13
5.4 Amélioration
Je montre que si p divise 232 + 1, p − 1 est multiple de 128. Pour cela,
il suffit de montrer que si on a p ≡ 1 (mod 8), 2 est un carré modulo p. En
effet, si 2 est le carré de a, on a 232 = a64 = −1 et a est d’ordre 128.
Pour cela, deux voies. Soit on sait que F∗p est cyclique d’ordre p − 1, donc
contient un élément ζ d’ordre 8, qui vérifie donc ζ 4 +1 = 0, donc ζ 2 +ζ −2 = 0,
et on voit que a = ζ + ζ −1 vérifie a2 = 2.
Soit on sait ça, mais on fait semblant de ne pas le savoir et on regarde une
racine huitième explicite, à savoir 28 et son inverse 256 = −224 et on montre
que a = 28 − 224 a pour carré 2. En effet, on a (28 − 224 )2 = 216 + 248 − 2.232
et cela résulte de 232 = −1.

6 Annexe 2, le grand nombre de Mersenne

Je montre que M := M6972593 = 2N − 1 commence par 437075 et finit par
193791.

6.1 Il finit par 193791

Il s’agit de calculer M modulo 106 . Le problème a été étudié ci-dessus,
le programme powerv donne instantanément le résultat : 26972593 ≡ 193792
(mod 106 ), d’où le résultat. Bien entendu, on peut aussi le faire à la main,
de proche en proche.

6.2 Il commence par 437075

On commence par calculer le nombre m de chiffres de M , ou de 2N . On a
l’encadrement : 10m−1 ≤ 2N < 10m et, en passant au logarithme, on trouve
(m − 1) ln 10 ≤ N ln 2 < m ln 10, d’où m = 2098960.
Si l’on veut calculer les 6 premiers chiffres de M , qui forment un nombre
p, on écrit alors l’encadrement :

p × 102098954 ≤ M < (p + 1) × 102098954

ce qui donne, en passant au logarithme, ln p = 12, 987862 et p = 437075.

7 Annexe 3, le nombre de Ramanujan

C’est le nombre 1729 = 123 + 13 = 103 + 93 . Ce nombre est un nombre de
Carmichaël, c’est-à-dire un nombre non premier (on a n = 1729 = 7 × 13 ×

14
19 = pqr) et qui pourtant vérifie le petit théorème de Fermat pour tous les
entiers : on a an ≡ a (mod n) pour tout a.
La preuve de c résultat est facile avec le lemme chinois. En effet, on a un
isomorphisme :

Z/1729Z ' Z/7Z × Z/13Z × Z/19Z.

Si maintenant on prend x ∈ Z/1729Z, on le décompose en x = (a, b, c) dans

le produit et on a xn = (an , bn , cn ). Il suffit de montrer qu’on a z n = z dans
les trois facteurs. C’est le fait que p − 1 = 6, q − 1 = 12 et r − 1 = 18 divisent
n − 1 = 123 . En effet, si a, b, c sont respectivement premiers à p, q, r on a
ap−1 ≡ 1 (mod p), bq−1 ≡ 1 (mod q) et cr−1 ≡ 1 (mod r), donc an−1 ≡ 1
(mod p) et de même pour les autres. On en déduit xn−1 ≡ 1 (mod n) et le
résultat. Si l’un des a, b, c n’est pas premier modulo p, q, r, il devient 0 dans le
quotient et vérifie évidemment, par exemple, an ≡ a (mod p) et la conclusion
reste valable.

8 Annexe 4, la factorisation de Fermat

8.1 Le problème
Rappelons la question de Mersenne :
Le nombre 100895598169 est-il premier ?
Voici la réponse de Fermat :
À cette question je réponds que ce nombre est composé et se fait du produit
des deux : 898423 et 112303 qui sont premiers. Je suis toujours, mon révérend
Père, votre très humble et très affectionné serviteur.
La question est : comment a-t-il fait ?

8.2 Une procédure bien connue de Fermat

8.2.1 Une citation
Je recopie ici un extrait d’une lettre du même Fermat au même Mersenne
en 1664 :
Cela posé, qu’un nombre me soit donné, par exemple 2027651281, on
demande s’il est premier ou composé, et de quels nombres il est composé,
au cas qu’il le soit. J’extrais la racine, pour connaı̂tre le moindre des dits
nombres, et trouve 45029 avec 40440 de reste, lequel j’ôte du double plus 1
de la racine trouvée, savoir de 90059 : reste 49619, lequel n’est pas carré,
parce qu’aucun carré ne finit par 19, et partant je lui ajoute 90061, savoir

15
2 plus 90059 qui est le double plus 1 de la racine 45029. Et parce que la
somme 139680 n’est pas encore carrée, comme on le voit par les finales, je
lui ajoute encore le même nombre augmenté de 2, savoir 90063 et je continue
ainsi d’ajouter tant que la somme soit un carré, comme on peut voir ici.
Ce qui n’arrive qu’à 1040400 ; qui est carré de 1020 et partant le nombre
donné est composé ; car il est aisé, par l’inspection des dites sommes, de voir
qu’il n’y a aucune qui soit nombre carré que la dernière, car les carrés ne
peuvent souffrir les finales qu’elles ont, si ce n’est 499944 qui néanmoins n’est
pas carré. Pour savoir maintenant les nombres qui composent 2027651281,
j’ôte le nombre que j’ai premièrement ajouté, savoir 90061, du dernier ajouté
90081. Il reste 20, à la moitié duquel plus 2, savoir à 12, j’ajoute la racine
premièrement trouvée 45029. La somme est 45041, auquel nombre ajoutant
et ôtant 1020, racine de la dernière somme 1040000, on aura 46061 et 44021,
qui sont les deux nombres plus prochains qui composent 2027651281. Ce sont
les seuls, parce que l’un et l’autre sont premiers.

8.2.2 Traduction
La procédure, dite avec des symboles17 , est donc la suivante. On a à
décomposer un nombre N . On en calcule la racine carrée et sa partie entière
q, ici q = 45029. On a donc q 2 ≤ N < (q + 1)2 . Si on a N = q 2 on a fini. Ici,
ce n’est pas le cas car on a N = q 2 + 40440. On pose r = N − q 2 .
L’idée, ensuite, est d’écrire N sous la forme N = (q + k)2 − s2 = (q +
k − s)(q + k + s). On essaie successivement avec k = 1, 2, ... et on s’arrête si
(q + k)2 − N est un carré. Par exemple pour k = 1, on regarde (q 2 + 2q +
1) − N = (2q + 1) − r. On retranche donc r = 40440 de 2q + 1 = 90059
comme le dit Fermat. Il reste 49619 qui n’est toujours pas un carré. Comme
on a 2kq + k 2 = 2(k − 1)q + (k − 1)2 + (2q + 2k − 1), on continue en ajoutant
2q + 3, 2q + 5, ..., 2q + 2k − 1, jusqu’à ce qu’on trouve un carré. Ici, il faut
aller jusqu’à k = 12 :
2q + 1 − r + (2q + 3) + (2q + 5) + · · · + (2q + 23) = 1040400 = (1020)2 = s2 .
On a donc N = (q + k)2 − s2 = (45029 + 12)2 − 10202 = 44021 × 46061.

8.2.3 La méthode de Fermat dite à ma manière

Il s’agit de décomposer le nombre√ N en produit de facteurs premiers. On
suppose N impair. On pose q = [ N ] et on suppose que N n’est pas un
carré. On a donc q 2 < N < q 2 + 2q + 1. On cherche une décomposition de N
sous la forme N = (q + a)(q + b) avec a, b ∈ Z.
17
Et l’on voit ici quelle économie de pensée ils procurent !

16
8.1 Lemme. Si on a une décomposition comme ci-dessus :
• a et b sont de même parité,
• a et b sont non nuls et de signes contraires, sauf si l’on a N = q(q + 2),
• on a ab ≤ 0 et a + b > 0.

Démonstration. Comme N est impair il en est de même de q + a et q + b et

on a donc a ≡ q + 1 et b ≡ q + 1 modulo 2.
Si a, b sont tous deux ≤ 0 on a (q + a)(q + b) ≤ q 2 < N , s’ils sont tous
deux > 0 on a (q +a)(q +b) ≥ q 2 +2q +1 > N . Ces cas sont donc impossibles.
Il reste à examiner le cas où l’un des deux, disons a, est nul et l’autre > 0.
Comme on a q(q + b) ≤ q 2 + 2q on a b ≤ 2 et donc b = 2 à cause de la parité.
Pour le dernier point, il est clair que ab est ≤ 0. On a donc q 2 < N =
q 2 + (a + b)q + ab ≤ q 2 + (a + b)q, ce qui montre que a + b est > 0.

On cherche donc a, b tels que N − q 2 = (a + b)q + ab et on sait que a + b

est pair et ab ≥ 0. Pour cela, on effectue une pseudo-division euclidienne en
écrivant N − q 2 = 2nq − rn , avec n ∈ N∗ et rn < 0, mais sans imposer la
condition |rn | < q.
On aura la factorisation cherchée si l’on peut résoudre en a, b ∈ Z les
équations a + b = 2n et ab = −rn . Les nombres a, b sont racines de l’équation
X 2 − 2nX − rn = 0 et cette équation admet des solutions entières si et
seulement si son discriminant (réduit) ∆n = n2 + rn est un carré.
Pour faire ce calcul de proche en proche, on peut, comme Fermat, utiliser
une formule de récurrence : ∆n+1 = ∆n + 2q + 2n + 1 (qui résulte de rn+1 =
rn + 2q).
La validité de la méthode est donnée par le lemme suivant :

8.2 Lemme. On suppose que N est produit de deux nombres premiers p1 p2 .

Soit A la “patience” de l’utilisateur (c’est-à-dire le nombre d’essais qu’il est
prêt à faire pour mettre en œuvre la méthode). La méthode de Fermat donne
p1 + p2 √
un résultat pourvu que la moyenne m = diffère de q = [ N ] de
2
moins de A.
a+b
Démonstration. Si on a N = (q + a)(q + b), la moyenne est m = q + .
2
Un succès de la tentative correspond à l’écriture N − q 2 = 2nq − rn , avec
a+b
n= = m − q et il doit être obtenu avec n ≤ A, d’où le résultat.
2
8.3 Remarques. 1) Si N = q(q + 2), on a N − q 2 = 2q et la factorisation est
obtenue dès la première opération.

17
 2) Le cas le plus favorable après celui-ci est celui où le succès est obtenu
avec n = 1. Dans ce cas, l’écriture N − q 2 = 2q − r est la division euclidienne
de N − q 2 par 2q (avec reste r négatif mais tel que |r| < 2q).
Attention, l’exemple de N = q 2 + q − s avec 0 < s < q et q + s + 1 carré
comme N = 65, q = 8, r = 7 montre que N − q 2 = 2q − (q + s) n’est pas
nécessairement la division euclidienne de N − q 2 par q.

8.3 Une hypothèse sur la décomposition de 100895598169 ?

8.3.1 Le principe
L’idée est très voisine de celle de la méthode précédente. On part d’un
entier N et on suppose qu’il √ est impair et que ce n’est pas un carré.
p Au lieu de
regarder seulement q = [ N ], on regarde tous les nombres q = [ N/k] pour
k = 1, 2, . . ., jusqu’à la patience de l’utilisateur. On cherche ensuite, avec le
nombre q en question, une décomposition de la forme N = (kq + a)(q + b) =
kq 2 + (kb + a)q + ab. Précisément :

8.4 Proposition. On suppose que N est produit de deux nombres premiers

p1 p2 . Soit A la “patience” de l’utilisateur (c’est-à-dire le nombre d’essais qu’il
est prêt à faire pour mettre en œuvre la méthode). On suppose qu’il existe
p √
k ≤ A tel que, si q = [ N/k], on ait p1 = kq + a et p2 = q + b avec |a| < q
√
et |b| < q. On trouve alors la décomposition en effectuant les divisions
euclidiennes de N − kq 2 par q pour k ≤ A.

Démonstration. Si on a N = (kq + a)(q + b), on a N − kq 2 = (kb + a)q + ab.

Comme on a supposé |ab| < q, la division euclidienne de N − kq 2 par q donne
kb+a comme quotient et ab comme reste (éventuellement négatif) et, comme
k est connu, on en déduit a, b donc p1 et p2 .

8.5 Remarque. Si l’on est dans cette situation, on a N − q 2 = q(kb + a) + ab

avec |ab| < q et le quotient approché de N − q 2 par q est proche de l’entier
kb + a. C’est ainsi qu’on peut repérer les cas propices à un essai.

8.3.2 Application à Fermat et Mersenne

p
Pour k = 1, 2, . . . on calcule q = [ N/k], puis le quotient approché de
N − kq 2 par q et on regarde si ce quotient est proche d’un entier. On obtient
successivement, pour k = 1, . . . , 7 les quotients suivants : 1, 34 ; 3, 5 ; 5, 57 ;
2, 69 ; 2, 28 ; 3, 14 ; 12, 46, tous assez éloignés des entiers.

18
 N − kq 2
En revanche, pour k = 8, on a q = 112302, et ' 15, 0000623.
q
On écrit donc :

100895598169 − 8 × 1123022 = 15 × 112302 + 7.

Il reste à résoudre les équations : 8b + a = 15 et ab = 7, ce qui donne

évidemment a = 7 et b = 1. On obtient la décomposition N = p1 p2 avec
p1 = kq + a = 898423 et p2 = q + b = 112303.

19