65537 (tall)

Fra Wikipedia, den frie encyklopedi
Hopp til: navigasjon, søk
65537
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[rediger | rediger kilde]

65537 er det største kjente primtallet på formen (). 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

[1]

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

I 1880 viste Fortuné Landry at

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

Anvendelser[rediger | rediger kilde]

65537 er ofte brukt som en offentlig eksponent i RSA-kryptosystemet. Fordi det er det fermattallet Fn = 22n + 1 med n = 4, er den vanlige forkortelsen "F4" 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[rediger | rediger kilde]

  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
  3. ^ «genrsa(1)». OpenSSL Project. «-F4|-3 [..] the public exponent to use, either 65537 or 3. The default is 65537.»