65537 (number)

From Wikipedia, the free encyclopedia
Jump to: navigation, search
65536 65537 65538
Cardinal sixty-five thousand five hundred thirty-seven
Ordinal 65537th
(sixty-five thousand five hundred and thirty-seventh)
Factorization 65537
Prime Yes
Roman numeral LXVDXXXVII
Binary 100000000000000012
Ternary 100222200223
Quaternary 1000000014
Quinary 40441225
Senary 12232256
Octal 2000018
Duodecimal 31B1512
Hexadecimal 1000116
Vigesimal 83GH20
Base 36 1EKH36
Construction of a regular 65537-gon. See constructible polygon.

65537 is the integer after 65536 and before 65538.

In mathematics[edit]

65537 is the largest known prime number of the form 2^{2^{n}} +1, where n = 4. Therefore a regular polygon with 65537 sides is constructible with compass and unmarked straightedge. 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,

2^{2^{1}} + 1= 2^{2} +1 = 5,

2^{2^{2}} + 1 = 2^{4} +1 = 17,

2^{2^{3}} + 1= 2^{8} + 1= 257,

2^{2^{4}} + 1 = 2^{16} + 1 = 65537.[1]

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

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 \times 67280421310721

65537 is also the 17th Jacobsthal–Lucas number, and the largest integer n for which the number 10^{n} + 27 is a probable prime.[2]

Applications[edit]

65537 is commonly used as a public exponent in the RSA cryptosystem. Because it is the Fermat number Fn = 22n with n = 4, the common shorthand is "F4" or "F4".[3] This value is seen as a wise compromise, since it is famously known to be prime, large enough to avoid the attacks to which small exponents make RSA vulnerable, and due to its low Hamming weight (number of 1 bits) can be computed extremely quickly on binary computers, which often support shift and increment instructions. Exponents in any base can be represented as shifts to the left in a base positional notation system, and so in binary the result is doubling—65537 is the result of incrementing shifting 1 left by 16 places, and 16 is itself obtainable without loading a value into the register (which can be expensive when register contents approaches 64 bit), but zero and one can be derived more 'cheaply'.

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[edit]

  1. ^ Conway, J. H.; Guy, R. K. (1996). The Book of Numbers. New York: Springer-Verlag. p. 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."