65537 (число)

65537 – це ціле число після 65536 і перед 65538.

65537 – це найбільше відоме просте число вигляду ${\displaystyle 2^{2^n}+1}$ (${\displaystyle n=4}$), і, найімовірніше, є останнім^[1]. Отже, правильний 65537-кутник можна побудувати за допомогою циркуля та лінійки без поділок. Йоганн Густав Гермес навів перший явний спосіб побудови цього багатокутника. У теорії чисел прості числа такого вигляду відомі як прості числа Ферма, названі на честь математика П'єра Ферма. Єдиними відомими простими числами Ферма є

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

У 1732 році Леонард Ейлер виявив, що наступне число Ферма є складеним:

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

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

У 1880 році Фортюне Ландрі показав, що 65537 також є 17-м числом Якобсталя-Люка і наразі є найбільшим відомим цілим числом n, для якого число ${\displaystyle 10^n+27}$ є ймовірним простим числом^[3].

Число 65537 зазвичай використовується як публічний показник степеня в криптосистемі RSA. Оскільки воно є числом Ферма F_n = 2²ⁿ + 1 при n = 4, для нього часто використовують скорочення "F₄" або "F4"^[4]. Це значення застосовувалося в RSA переважно з історичних причин; ранні реалізації RSA (без належного доповнення) були вразливими до дуже малих показників степеня, тоді як використання високих показників степеня потребувало значних обчислювальних витрат і не давало жодних переваг для безпеки (за умови належного доповнення)^[5].

Число 65537 також використовується як модуль у деяких генераторах випадкових чисел Лемера, наприклад, у тому, що застосовувався в ZX Spectrum^[6], що гарантує взаємну простоту будь-якого початкового значення з цим модулем (це необхідно для забезпечення максимального періоду), а також дозволяє ефективно виконувати редукцію за модулем за допомогою бітового зсуву та віднімання.