Книга: Кому нужна математика? Понятная книга о том, как устроен цифровой мир
Назад: Сила абстрактного подхода к шифрованию
Дальше: Открытый обмен ключами
Простые числа
Как вы уже поняли, шифрование имеет дело с числами и преобразованиями чисел. Этими вопросами в математике занимается теория чисел, один из классических, даже древних разделов математики. Казалось бы, зачем изучать числа? Лучшие математические умы занимались этой наукой, движимые чистым любопытством. Просто потому, что математики любят числа и любят отыскивать их скрытые закономерности. Умственные изощрения математиков с веками усложнялись без какой-либо перспективы для серьезного применения. И вдруг…
И вдруг в XX веке весь мир перешел на цифровые технологии! Наш бизнес, наше информационное обеспечение, даже наше общение и, конечно, наши секреты – все кодируется, шифруется и пересылается в виде чисел! Любимое хобби математиков неожиданно превратилось в жизненно важный источник знаний об основе современной жизни – числе.
В теории чисел особую роль играют так называемые простые числа. Простые числа знакомы нам со школы. Это числа, которые делятся только на единицу и на само себя. Многие узнают этот знаменитый ряд:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31…
Все простые числа, кроме двойки, нечетные. И это понятно, потому что четные числа делятся на два.
Еще со времен древнегреческого математика Евклида известно, что простых чисел бесконечное множество. Однако устроены они крайне сложно, и в теории чисел было брошено немало усилий на изучение их свойств. Ниже во врезке для интересующегося читателя мы приводим несколько любопытных фактов, касающихся простых чисел. Этот материал не требует математической подготовки, но и не влияет на наш дальнейший рассказ, поэтому при желании можете его пропустить.
Несколько интересных свойств простых чисел
Простых чисел, которые не превосходят п, примерно
где ln(n) это натуральный логарифм. Заметим, что ln(n) растет гораздо медленнее, чем п. Получается, что простые числа попадаются довольно часто. По этой оценке, их количество от одного до миллиарда равно примерно 48 254 942. На самом деле таких чисел 50 847 534, то есть оценка вполне точная. Первым, кто добился серьезных продвижений в получении подобных оценок, был наш замечательный математик Пафнутий Львович Чебышев (1821–1894).Есть и такой забавный результат: между х и 2х всегда находится простое число. Это так называемый постулат Бертрана. Однако проблема его уточнения очень сложна, а именно: верно ли, что между х и 1,1х есть простые числа (хотя бы при больших x)? Верно ли, что они есть между х и x + √x? Первое верно, а о втором никто не знает.Все верят в бесконечность числа «простых близнецов»: 11 и 13, 17 и 19, 29 и 31 и так далее. Но пока никто не может это доказать.
Важно понимать, что никаких формул для поиска простых чисел не существует в принципе! Простые числа распределены очень хитро. Как мы скоро увидим, они крайне важны на практике, особенно сверхбольшие простые числа. Целая индустрия, привлекающая как математиков, так и программистов, занимается построением все новых и новых простых чисел. Так, в январе 2016 года было найдено очередное простое число, равное 274207281−1. В нем 22 338 618 знаков! Нечто запредельное…
Назад: Сила абстрактного подхода к шифрованию
Дальше: Открытый обмен ключами
