65 537

65 537 est le nombre entier suivant 65 536 et précédant 65 538. C'est un nombre premier et un nombre de Fermat, et le plus grand nombre connu possédant ces deux propriétés.

Mathématiques

Construction d'un polygone régulier de 65 537 côtés (voir « Polygone constructible »).

65 537 est le plus grand nombre premier connu de la forme 2 2 n + 1 {\displaystyle 2^{2^{n}}\!+1} (n = 4). Ainsi, un polygone régulier à 65 537 côtés peut être construit à la règle et au compas ; la première construction explicite est obtenue en 1894 par Johann Gustav Hermes (en)[1]. En théorie des nombres, les nombres premiers de cette forme sont appelés nombres premiers de Fermat, du nom du mathématicien français Pierre de Fermat. Les seuls nombres premiers de Fermat connus sont :

  • 2 2 0 + 1 = 2 1 + 1 = 3 {\displaystyle 2^{2^{0}}\!+1=2^{1}\!+1=3}  ;
  • 2 2 1 + 1 = 2 2 + 1 = 5 {\displaystyle 2^{2^{1}}\!+1=2^{2}\!+1=5}  ;
  • 2 2 2 + 1 = 2 4 + 1 = 17 {\displaystyle 2^{2^{2}}\!+1=2^{4}\!+1=17}  ;
  • 2 2 3 + 1 = 2 8 + 1 = 257 {\displaystyle 2^{2^{3}}\!+1=2^{8}\!+1=257}  ;
  • 2 2 4 + 1 = 2 16 + 1 = 65537 {\displaystyle 2^{2^{4}}\!+1=2^{16}\!+1=65537} [2].

Leonhard Euler découvre en 1732 que le nombre de Fermat suivant est un nombre composé :

2 2 5 + 1 = 2 32 + 1 = 4294967297 = 641 × 6700417 {\displaystyle 2^{2^{5}}\!+1=2^{32}\!+1=4294967297=641\times 6700417} ,

et Fortuné Landry en 1880 qu'il en est de même pour celui d'après :

2 2 6 + 1 = 2 64 + 1 = 274177 × 67280421310721 {\displaystyle 2^{2^{6}}\!+1=2^{64}\!+1=274177\times 67280421310721} .

65 537 est également le 17e nombre de Jacobsthal-Lucas, et le plus grand entier n connu tel que 10 n + 27 {\displaystyle 10^{n}\!+27} soit un nombre premier probable[3].

Applications

65 537 est couramment utilisé comme exposant public dans le chiffrement RSA. Comme il s'agit du nombre de Fermat F n = 2 2 n + 1 {\displaystyle F_{n}=2^{2^{n}}+1} avec n = 4 {\displaystyle n=4} , le raccourci courant est F 4 {\displaystyle F_{4}} ou F 4 {\displaystyle F4} [4]. Cette valeur a été utilisée dans le chiffrement RSA principalement pour des raisons historiques ; les premières implémentations de chiffrement RSA brutes (sans rembourrage approprié) étaient vulnérables aux très petits exposants, tandis que l'utilisation d'exposants élevés était coûteuse en calculs sans aucun avantage pour la sécurité (en supposant un rembourrage approprié)[5].

65 537 est également utilisé comme module dans certains générateurs de nombres aléatoires de Lehmer, comme celui utilisé par ZX Spectrum[6], qui garantit que toute valeur de départ sera copremiers (essentielle pour assurer la période maximale) tout en permettant une réduction efficace par le module en utilisant un décalage de bit et une soustraction.

Références

  • (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « 65,537 » (voir la liste des auteurs).
  1. (de) Johann Gustav Hermes (en), « Über die Teilung des Kreises in 65537 gleiche Teile », Nachrichten von der Gesellschaft der Wissenschaften zu Göttingen, Mathematisch-Physikalische Klasse, Göttingen, vol. 3,‎ , p. 170–186 (lire en ligne).
  2. (en) J. H. Conway et R. K. Guy, The Book of Numbers, New York, Springer-Verlag, (ISBN 0-387-97993-X, lire en ligne Inscription nécessaire), 139
  3. (en) « Sequences by difficulty of search » [archive du ] (consulté le )
  4. (en) « genrsa(1) » [archive du ], OpenSSL Project (consulté le ) : « -F4|-3 [..] the public exponent to use, either 65537 or 3. The default is 65537. »
  5. (en) « RSA with small exponents? »
  6. (en) Steve Vickers, Sinclair ZX Spectrum Basic Programming, 2nd, , 73–75 p. (lire en ligne), « Chapter 11. Random numbers » :

    « The ZX Spectrum uses p=65537 and a=75, and stores some bi-1 in memory. »

  • icône décorative Arithmétique et théorie des nombres