65537 (tall)

65537
← 65536 65538 →
Faktorisert		primtall
Romertall		LXVDXXXVII
Binærtall		10000000000000001
Oktaltall		200001
Heksadesimaltall		10001
Se også årstallet 65537

65 537 er det 4. fermattallet og det største kjente fermattallet som er et primtall. 65 537 har blitt brukt som modulus i tallteoretiske transformasjoner.

Konstruksjon av en regulær 65537-gon. Se konstruerbar polygon.

65537 er heltallet etter 65536 og før 65538.

I matematikk

65537 er det største kjente primtallet på formen ${\displaystyle 2^{2^{n}}+1}$ (${\displaystyle n=4}$). Derfor er en regulær polygon med 65537 sider konstruerbar med passer og umerket linjal. I tallteori er primtall på denne formen kjent som fermatprimtall, oppkalt etter matematikeren Pierre de Fermat.

De eneste kjente fermatprimtallene er

${\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.}$^[1]

I 1732 fant Leonhard Euler ut at det neste fermattallet er sammensatt:

${\displaystyle 2^{2^{5}}+1=2^{32}+1=4294967297=641\times 6700417}$

I 1880 viste Fortuné Landry at

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

65537 er også det 17. Jacobsthal–Lucas-tallet, og for tiden (2017) det største kjente heltallet n som gjør tallet ${\displaystyle 10^{n}+27}$ til et sannsynlig primtall (probable prime).^[2]

Anvendelser

65537 er ofte brukt som en offentlig eksponent i RSA-kryptosystemet. Fordi det er det fermattallet F_n = 2²ⁿ + 1 med n = 4, er den vanlige forkortelsen "F₄" eller "F4".^[3] Denne verdien ses på som et klokt kompromiss, siden den er berømt for å være et primtall, stort nok til å unngå angrepene som små eksponenter gjør RSA sårbar for. På grunn av sin lave Hamming-vekt (antall 1-bits) kan den bli beregnet ekstremt hurtig på binære regnemaskiner, som ofte støtter skift- og inkrementinstruksjoner. Eksponenter i et hvilket som helst grunntall kan representeres som skift mot venstre i et posisjonelt grunntallsnotasjonssystem, så i totallssystemet er resultatet dobling—65536 er resultatet av inkrementell skifting av 1 med 16 plasser mot venstre, og 16 er i seg selv oppnåelig uten å laste en verdi inn i registeret (noe som kan være kostbart når registerinnholdet nærmer seg 64 bit), men null og én kan utledes "billigere".

65537 er også brukt som modulus i noen Lehmer-generatorer for tilfeldige tall, slik som den som brukes av ZX Spectrum, som sikrer at en hvilket som helst frøverdi vil bli relativt primisk til den, og effektiv reduksjon av modulusen ved hjelp av bitskift og subtraksjon er mulig.

Referanser

1. Conway, J. H.; Guy, R. K. (1996). The Book of Numbers. New York: Springer-Verlag. s. 139. ISBN 0-387-97993-X. 
2. «Sequences by difficulty of search». Arkivert fra originalen 14. juli 2014. Besøkt 3. mai 2017. 
3. «genrsa(1)». OpenSSL Project. Arkivert fra originalen 3. juni 2013. «-F4|-3 [..] the public exponent to use, either 65537 or 3. The default is 65537.» 

Autoritetsdata