Как математики рисуют картины простыми числами
Всем нам знакомы простые числа, вот они слева направо: 2, 3, 5, 7, 11, 13, и так далее. И чем дальше, тем реже в ряду натуральных чисел попадаются простые — например, среди первой сотни есть 25 простых чисел, а между 10 000 и 10 100 простых уже всего шесть: 10 003, 10 019, 10 043, 10 049, 10 057 и 10 069.
Тем не менее, доля простых убывает достаточно медленно: среди n-значных чисел простых примерно одно из каждых 2,3n. И это непраздное знание: для известного алгоритма шифрования RSA необходимо выбрать два простых числа, которые нельзя было бы подобрать перебором. Обычно это делают, перебирая случайно взятые числа из сотен десятичных знаков, пока не наткнутся на простое (и исключая «слишком специальные» числа). Но нужно еще проверить число на простоту!
Относительно большая доля простых чисел означает также, что у конкретного большого числа, скорее всего, можно просто подкрутить несколько цифр — и получить простое. Это простое замечание породило целое направление: псевдографику, в которой картина изображается в виде простого числа.
Самый знаменитый (и, видимо, самый первый) пример такой картины — это простое число, изображающее герб Тринити Холла, одного из старейших колледжей Кембриджа, среди выпускников которого, например, Стивен Хокинг. Его в свое время обнаружил математик Джеймс Макки (James McKee), оно состоит из 1350 цифр (это год основания колледжа), и выглядит вот так.
С ростом вычислительной мощности компьютеров и упрощения доступа к библиотекам для работы с большими числами создавать такие изображения стало проще. Вот примеры:
В работе Закари Абеля (Zachary Abel) есть потрет Софи Жермен, полученный закрашиванием простого числа Софи Жермен (таким простым p, что 2p + 1 тоже простое).
А если сопоставить с цифрами цветовую палитру, можно найти простое число, которое будет выглядеть, как «Звездная ночь» или «Большая волна в Канагаве».
Самое сложное при работе с такими картинками — это, собственно, проверка найденных чисел на простоту. Как проверить на простоту 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. Такие числа называют числами Кармайкла; первые из них это:
Другой признак, тоже неопровержимо свидетельствующий о том, что число 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-значное число можно проверить на простоту за полиномиальное по количеству знаков время без дополнительных предположений, было доказано уже в нашем тысячелетии.
И напоследок — еще одно простое число, десятичная запись которого состоит из нулей и единиц: