Misplaced Pages

65,537

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
(Redirected from 65537 (number)) Natural number
← 65536 65537 65538 →
← 0 10k 20k 30k 40k 50k 60k 70k 80k 90k →
Cardinalsixty-five thousand five hundred thirty-seven
Ordinal65537th
(sixty-five thousand five hundred thirty-seventh)
Factorizationprime
Prime6,543rd
Greek numeral M ϝ {\displaystyle {\stackrel {\digamma }{\mathrm {M} }}} ͵εφλζ´
Roman numeralLXVDXXXVII
Binary100000000000000012
Ternary100222200223
Senary12232256
Octal2000018
Duodecimal31B1512
Hexadecimal1000116
Construction of a regular 65537-gon. See constructible polygon.

65537 is the integer after 65536 and before 65538.

In mathematics

65537 is the largest known prime number of the form 2 2 n + 1 {\displaystyle 2^{2^{n}}+1} ( n = 4 {\displaystyle n=4} ), and is most likely the last one. Therefore, a regular polygon with 65537 sides is constructible with compass and unmarked straightedge. Johann Gustav Hermes gave the first explicit construction of this polygon. In number theory, primes of this form are known as Fermat primes, named after the mathematician Pierre de Fermat. The only known prime Fermat numbers are

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

In 1732, Leonhard Euler found that the next Fermat number is composite:

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

In 1880, Fortuné Landry [fr] showed that

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

65537 is also the 17th Jacobsthal–Lucas number, and currently the largest known integer n for which the number 10 n + 27 {\displaystyle 10^{n}+27} is a probable prime.

Applications

65537 is commonly used as a public exponent in the RSA cryptosystem. Because it is the Fermat number Fn = 2 + 1 with n = 4, the common shorthand is "F4" or "F4". This value was used in RSA mainly for historical reasons; early raw RSA implementations (without proper padding) were vulnerable to very small exponents, while use of high exponents was computationally expensive with no advantage to security (assuming proper padding).

65537 is also used as the modulus in some Lehmer random number generators, such as the one used by ZX Spectrum, which ensures that any seed value will be coprime to it (vital to ensure the maximum period) while also allowing efficient reduction by the modulus using a bit shift and subtract.

References

  1. Boklan, Kent D.; Conway, John H. (2017). "Expect at most one billionth of a new Fermat Prime!". The Mathematical Intelligencer. 39 (1): 3–5. arXiv:1605.01371. doi:10.1007/s00283-016-9644-3. S2CID 119165671.
  2. Conway, J. H.; Guy, R. K. (1996). The Book of Numbers. New York: Springer-Verlag. p. 139. ISBN 0-387-97993-X.
  3. "Sequences by difficulty of search". Archived from the original on 2014-07-14. Retrieved 2014-06-14.
  4. "genrsa(1)". OpenSSL Project. Archived from the original on 2017-03-13. Retrieved 2017-05-24. -F4|-3 the public exponent to use, either 65537 or 3. The default is 65537.
  5. "RSA with small exponents?".
  6. Vickers, Steve (1983). "Chapter 11. Random numbers". Sinclair ZX Spectrum Basic Programming (2nd ed.). Sinclair Research Ltd. pp. 73–75. Retrieved 2022-05-26. The ZX Spectrum uses p=65537 and a=75, and stores some bi-1 in memory.
Category: