65537 (tall)

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.

65537 er heltallet etter 65536 og før 65538.

I matematikk

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

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

Anvendelser
65537 er ofte brukt som en offentlig eksponent i RSA-kryptosystemet. Fordi det er det fermattallet  med , er den vanlige forkortelsen "F" eller "F4".   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

Kategori:Naturlige tall
Kategori:Primtall