Кому нужна математика? Понятная книга о том, как устроен цифровой мир (Литвак, Райгородский) - страница 50
Простых чисел, которые не превосходят п, примерно
где ln(n) это натуральный логарифм. Заметим, что ln(n) растет гораздо медленнее, чем п. Получается, что простые числа попадаются довольно часто. По этой оценке, их количество от одного до миллиарда равно примерно 48 254 942. На самом деле таких чисел 50 847 534[15], то есть оценка вполне точная. Первым, кто добился серьезных продвижений в получении подобных оценок, был наш замечательный математик Пафнутий Львович Чебышев (1821–1894).
Есть и такой забавный результат: между х и 2х всегда находится простое число. Это так называемый постулат Бертрана. Однако проблема его уточнения очень сложна, а именно: верно ли, что между х и 1,1х есть простые числа (хотя бы при больших x)? Верно ли, что они есть между х и x + √x? Первое верно, а о втором никто не знает.
Все верят в бесконечность числа «простых близнецов»: 11 и 13, 17 и 19, 29 и 31 и так далее. Но пока никто не может это доказать.
Важно понимать, что никаких формул для поиска простых чисел не существует в принципе! Простые числа распределены очень хитро. Как мы скоро увидим, они крайне важны на практике, особенно сверхбольшие простые числа. Целая индустрия, привлекающая как математиков, так и программистов, занимается построением все новых и новых простых чисел. Так, в январе 2016 года было найдено очередное простое число, равное 2>74207281−1. В нем 22 338 618 знаков! Нечто запредельное…
Открытый обмен ключами
В настоящее время особенно популярны так называемые схемы шифрования с открытым ключом. Мы расскажем о схеме Диффи – Хеллмана, которая датируется 1970-ми годами и активно используется на практике. Эта схема основана на глубокой математике, но саму идею понять совсем несложно.
Возьмем простое число р. В реальности оно должно быть огромным, но для примера выберем маленькое простое число 19. Теперь выберем еще одно число g, тоже целое, но необязательно простое и меньше р. Например, g = 2.
Числа р и g знают все: и Алиса, и Боб, и даже Ева. Теперь Алиса выбирает число х, например x = 6, и хранит его в тайне. Боб выбирает число у, скажем y = 8, и тоже никому его не сообщает.
Дальше начинается шифрование. Алиса находит остаток от деления на р числа g>х:
2>6 = 64,
64÷19 = 3 и 7 в остатке.
Боб делает то же самое со своим задуманным числом:
2>8 = 256,
256÷19 = 13 и 9 в остатке.
Итак, наше преобразование выглядит следующим образом: возвести 2 в степень х и взять остаток от деления на 19. Мы изобразили это преобразование в общем виде на рис. 6.3. Напомним, что числа