Простые числа, такие как 2, 3, 5, 7, 11, 13 и последующие, являются фундаментальными объектами в теории чисел. Их частота встречаемости среди натуральных чисел убывает по мере увеличения величины чисел. Так, среди первых ста чисел terdapat 25 простых чисел, а в интервале от 10 000 до 10 100 их количество сокращается до шести: 10 003, 10 019, 10 043, 10 049, 10 057 и 10 069. Несмотря на это, плотность простых чисел среди n-значных чисел медленно убывает, приблизительно составляя одно из каждых 2,3n. Это свойство имеет важное значение в криптографии, например, в алгоритме шифрования RSA, где требуется выбор двух больших простых чисел, которые сложно было бы найти методом перебора. Обычно для этого используются случайные числа с сотнями десятичных знаков, пока не будет найдено простое число (исключая “особые” числа). После этого необходимо провести проверку найденного числа на простоту.
Относительно большая доля простых чисел означает также, что у конкретного большого числа, скорее всего, можно просто подкрутить несколько цифр — и получить простое. Это простое замечание породило целое направление: псевдографику, в которой картина изображается в виде простого числа.
Самый знаменитый (и, видимо, самый первый) пример такой картины — это простое число, изображающее герб Тринити Холла, одного из старейших колледжей Кембриджа, среди выпускников которого, например, Стивен Хокинг. Его в свое время обнаружил математик Джеймс Макки (James McKee), оно состоит из 1350 цифр (это год основания колледжа), и выглядит вот так.
Число Тринити холла. StackExchange
С ростом вычислительной мощности компьютеров и упрощения доступа к библиотекам для работы с большими числами создавать такие изображения стало проще. Вот примеры:
Gilles Esposito-Farese
В работе Закари Абеля (Zachary Abel) есть потрет Софи Жермен, полученный закрашиванием простого числа Софи Жермен (таким простым p, что 2p + 1 тоже простое).
Zachary Abel
А если сопоставить с цифрами цветовую палитру, можно найти простое число, которое будет выглядеть, как «Звездная ночь» или «Большая волна в Канагаве».
Roland Meertens
Самое сложное при работе с такими картинками — это, собственно, проверка найденных чисел на простоту. Как проверить на простоту 200-значное число N? О том, чтобы перебрать все возможные делители от единицы до 100-значного корня из N, не может быть и речи: даже если бы Земля состояла только из современных компьютеров, занятых только этой задачей, это все равно потребовало бы больше времени, чем прошло с момента Большого Взрыва.
Поэтому проверка на простоту больших чисел опирается на более сложные признаки. Одним из таких признаков является Малая теорема Ферма: если N простое, то для любого b его степень bN дает при делении на N тот же остаток, что и само b. Например, число 11 простое, и 211 = 2048 при делении на 11 дает остаток 2.
Поэтому, если для какого-то b разница bN− b не делится на N, то это гарантирует, что N составное (то есть не простое). Можно сказать, что число b выступает неопровержимым свидетелем не-простоты N.
А что, если различные b — например, выбираемые случайно, — раз за разом отказываются свидетельствовать о не-простоте N? Можно ли отсюда сделать вывод, что N простое? Увы — нет. Есть и составные числа N, для которых bN — b всегда делится на N. Такие числа называют числами Кармайкла; первые из них это:
- 561 = 3 × 11 × 17,
- 1105 = 5 × 13 × 17,
- 1729 = 7 × 13 × 19.
Тут была ошибка, мы ее исправили
Другой признак, тоже неопровержимо свидетельствующий о том, что число N составное — это наличие «лишнего» корня у квадратного уравнения. Например, если у уравнения x2 = 1 по модулю N есть решение x, не сравнимое ни с 1, ни с (-1), то N точно составное. Действительно, x² − 1 = (x − 1)(x + 1) делится на N, и если бы N было простым, то на него делился бы хотя бы один из сомножителей. Но как такой лишний квадратный корень найти?
Можно скрестить поиск корня из единицы с малой теоремой Ферма, получив достаточно надежный (хоть и вероятностный) тест Миллера-Рабина. Малую теорему Ферма для простого N можно переформулировать, «сократив» на b: если взято любое b от 1 до N − 1, то bN − 1 сравнимо с 1 по модулю N. Возведение же в (четную) степень N − 1 можно разбить на два этапа, записав показатель как N − 1 = 2d × m, где m нечетное. Тогда
bN − 1 = (bm)2^d = (((bm)2)2…)2.
Если bN − 1 не сравнимо с 1 по модулю N, то мы уже знаем, что N − не простое. Но если bN − 1 сравнимо с 1 по модулю N, то в цепочке возведений в квадрат
bm -> b2m -> b4m ->… -> b2^d × m = bN − 1
можно посмотреть на последний не-единичный элемент (если такой есть). И если это не (-1) по модулю N, то N — составное.
И наконец, если b от 2 до N — 1 взять случайным — то шанс, что (любое) составное N не будет «разоблачено» при такой процедуре, составляет не больше ¼ (а на самом деле гораздо меньше). Соответственно, шанс, что составное число проскочит сотню повторений такой процедуры, не больше, чем 4-100, то есть примерно 10-60.
Кстати — при некоторых, довольно правдоподобных, предположениях (если справедлива обобщенная гипотеза Римана), тест Миллера-Рабина можно сделать и детерминированным — оказывается, что достаточно проверить все не слишком большие остатки b. А то, что n-значное число можно проверить на простоту за полиномиальное по количеству знаков время без дополнительных предположений, было доказано уже в нашем тысячелетии.
И напоследок — еще одно простое число, десятичная запись которого состоит из нулей и единиц:
Автор: Сергей Кузнецов
Источник: https://nplus1.ru/
