ChronoMath, une chronologie des MATHÉMATIQUES
à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges

Cryptographie, cryptologie

La cryptographie est la technique (l'art ?) de communiquer au moyens de messages codés (on dit aussi chiffrés, car ce sont des méthodes numériques qui sont aujourd'hui principalement utilisées), les clés de décodage n'étant (en principe...) connues que des seuls correspondants.

C'est un vaste et complexe sujet, très en vogue de nos jours, car si elle fut utilisée naguère par les seuls militaires ou gouvernements, cette "science" nouvelle, on parle aujourd'hui de cryptologie, voit son application dans les problèmes de confidentialité liés aux télécommunications, à la sécurité bancaire, et à l'Internet en particulier (comptes en ligne, mails, SMS, ...).

L'arithmétique des grands nombres, aujourd'hui liée à l'analyse (intégration, séries numériques, courbes elliptiques, ...) y joue un rôle fondamental : nombres premiers, décomposition de grands nombres en produit de facteurs premiers (encodage RSA, » réf.8-11-12), nombres semi-premiers, nombres pratiques, nombres hautement composés, congruences arithmétiques, ...

Est qualifié de semi-premier (en anglais semiprime) ou presque premier (almost prime) voire bi-premier (biprime), tout entier naturel produit de deux nombres premiers éventuellement égaux.

• Par exemple 2018 est un nombre semi-premier : 2018 = 2 × 1009.

• 1009 est le plus petit entier premier supérieur à 1000. Le plus grand entier premier inférieur à 1000 étant 997.
               C'est ainsi que la précédente année semi-première contemporaine fut 1994.

• 1681 = 41² est semi-premier. D'une façon générale, par définition, tout carré d'un nombre premier est semi-premier.

 ➔  Ces définitions admettent un prolongement. Dans la littérature mathématique, on rencontre parfois la notion plus générale de nombre k-presque premier pour désigner un entier naturel produit de k nombres premiers (k ≥ 2) éventuellement égaux. Bien que cela n'ait guère de sens et d'intérêt, d'aucuns incluent k = 1 pour signifier les nombres premiers. Avec cette définition, 1681 et 2018 sont 2-presque premiers. 17, qui est premier, peut être considéré comme 1-presque premier.

∗∗∗
Pourriez-vous prouver ces deux résultats rencontrés sur la page d'Eric Weisstein consacrée aux nombres semi-premiers (» réf.7) :
Si n est semi-premier, n = pq, alors  p^q ≡ p [n].      »  petit théorème de Fermat
φ désignant la fonction caractéristique d'Euler (totient) : φ(n) = (p - 1)(q - 1).     » totient

Conjecture de Legendre :  »          Nombres de Mersenne :  »         Nombres pseudo-premiers : »

∗∗∗
send + more = money, un petit exercice niveau lycée
 

» Markov, Turing, Cook (et le problème P = NP)

 ➔   Pour en savoir plus :

1. Petite histoire de la cryptologie, page de Didier Muller : http://www.apprendre-en-ligne.net/crypto/histoire/index.html

2. Chiffrement & cryptographie, par Serge Delestan et Lionel Lejeune : http://nopb.chez.com/crypto.html

3. Cryptographie et codes secrets, sur le site de John Massa : http://www.mathmassa.free.fr/pdf/crypto_massa.pdf

4. Arithmétique et cryptographie, par Jean-Louis Nicolas (univ. Claude Bernard, Lyon) :
   http://math.univ-lyon1.fr/~nicolas/arithetcrypto.pdf

5. a) Codage et cryptographie, par Joan Gomez :
   https://images.math.cnrs.fr/Codage-et-cryptographie.html
   b) Comment les mathématiques ont envahi la cryptologie, par Marie-José Durand-Richard et Ph. Guillot (univ. Paris 8)
   - https://images.math.cnrs.fr/Comment-les-mathematiques-ont-investi-la-cryptologie-1.html
   - https://images.math.cnrs.fr/Comment-les-mathematiques-ont-investi-la-cryptologie-2.html

6. Sur le site d'Eric Weisstein :
   a/ Nombres semi-premiers  : http://mathworld.wolfram.com/Semiprime.html
   b/ Nombres presque premiers : http://mathworld.wolfram.com/AlmostPrime.html

7. An introduction to cryptography, par Richard A. Mollin (2007) :
   https://archive.org/stream/An_Introduction_to_Cryptography_Second_Edition#page/n3

8. Introductory Number Theory, par Michael Stoll (univ. Bayreuth), congruences, nombres premiers, cryptologie, encodage RSA ... :
   http://www.mathe2.uni-bayreuth.de/stoll/lecture-notes/IntroductoryNumberTheory.pdf

9. Factorisation par Maurice Margenstern : http://www.numdam.org/article/TAN_1985-1986__2__A6_0.pdf

10. Le second sujet du CAPES externe de mathématiques 2015 (chiffrement, codage) :
    http://irem.univ-reunion.fr/IMG/pdf/2015_capes_ep2_sujet.pdf
    » Le corrigé est à l'adresse : http://irem.univ-reunion.fr/IMG/pdf/2015_capes_ep2_corrige.pdf

11. Cryptographie et nombres premiers de Daniel Perrin (sur YouTube, 2016), univ. Paris Sud-Orsay :
    https://www.youtube.com/watch?v=dBTF2M3M1Uk

12. Algorithme RSA : https://openclassrooms.com/fr/courses/477751-lalgorithme-rsa/477335-chiffrer-et-dechiffrer