В одной из предыдущих статей я рассказал о математических алгоритмах, позволяющих проверить простоту очень большого числа. Но в основе всех тех алгоритмов лежит одна базовая операция — перемножение двух больших чисел. Именно операции длинного умножения занимают 99,9% времени выполнения любого теста простоты. Как же умножение реализуется на практике? Говорят, что при помощи быстрого преобразования Фурье. Но беглое прочтение Википедии вызывает недоумение. Какое отношение преобразование Фурье имеет к умножению целых чисел? Давайте разбираться.

Посмотрите на эту картинку. Она называется «скатерть Улама». Пиксели нумеруются из центра по спирали, и если номер пикселя — простое число, то он закрашивается чёрным. В глаза сразу бросаются диагональные линии. Если присмотреться, можно заметить горизонтальные и вертикальные линии. Что это? Простые числа вдруг подчиняются какому-то закону? Или же Вселенная пытается нам что-то сказать? Конечно же нет. Это наглядная иллюстрация того, что числовые последовательности могут иметь разный вес.

В предыдущей статье я рассказал об общих принципах поиска больших простых чисел. Но как бы ни был организован поиск, в конце он всегда заканчивается тестом простоты. И, к сожалению, иногда случается ситуация, когда простое число-то мы нашли, но доказать его простоту не можем. Например, так получилось с самым маленьким простым числом из миллиона цифр 10⁹⁹⁹⁹⁹⁹+593499. В этой статье я расскажу, почему тестам простоты уделяется так много внимания в сообществах добровольных распределённых вычислений, таких как GIMPS и PrimeGrid.

Самое большое простое число, известное на данный момент, состоит из почти 25 млн. цифр. Есть ли простые числа больше? Несомненно. Простых чисел бесконечное количество. Найдём ли мы простое число больше 25 млн. цифр? Тоже да, поиск не останавливается ни на секунду. Можно ли принять в нём участие? Конечно, достаточно присоединиться к одному из добровольных распределённых проектов по поиску больших простых чисел.