65 537

65 537 est le plus grand nombre premier connu de la forme ${\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 :

• ${\displaystyle 2^{2^{0}}\!+1=2^{1}\!+1=3}$ ;
• ${\displaystyle 2^{2^{1}}\!+1=2^{2}\!+1=5}$ ;
• ${\displaystyle 2^{2^{2}}\!+1=2^{4}\!+1=17}$ ;
• ${\displaystyle 2^{2^{3}}\!+1=2^{8}\!+1=257}$ ;
• ${\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é :

${\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 :

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

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

65 537 est couramment utilisé comme exposant public dans le chiffrement RSA. Comme il s'agit du nombre de Fermat ${\displaystyle F_{n}=2^{2^{n}}+1}$ avec ${\displaystyle n=4}$, le raccourci courant est ${\displaystyle F_{4}}$ ou ${\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.

• (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).

• Arithmétique et théorie des nombres