числа Мерсенна на пальцах, ч. 2
Итак, с лирическим отступлением покончено, пришло время разобраться, что, собственно, вообще происходит?
Жил-был во Франции математик Мерсенн, довольно крутой дядька, много чего сделавший в своё время для науки. Нас в данном случае будет интересовать только одно направление его деятельности - изучение свойств чисел, представляющих собой степени двойки минус единица. Было замечено, что некоторые из этих чисел простые, причём в каждом случае экспонента, то есть степень, в которую возводится двойка, при этом тоже представляла собой простое число.
Первые простые числа Мерсенна были найдены давным-давно, ещё вручную. Ф вот потом, когда количество цифр в ПЧМ перевалило за сотню, разумеется, стало понятно, что без ЭВМ не обойтись. К счастью, в 1878 году был разработан полиномиальный тест простоты, применимый именно для таких чисел, который настолько превосходил по скорости все другие, что вот уже долгое время звание самых больших известных человечеству простых чисел удерживают простые числа Мерсенна.
Переходя к практической части - проект распределённых вычислений GIMPS, который, собственно, уже третий десяток лет и занимается тем, что находит новые ПЧМ с помощью теста Люка-Лемера. Принцип работы следующий - волонтёры устанавливают на компьютер ПО, которое после первичной настройки автоматически получает задания с сервера проекта и отправляет туда результаты.
Задания можно разделить на две основные группы - тесты простоты и факторизация. Первая - представляет собой, собственно, проверку на простоту очередного числа Мерсенна с простой экспонентой. Факторизация - это попытка разложить число Мерсенна на множители, то есть доказать обратное (что число - не простое, а составное). Делается это для того, чтобы заранее сократить число претендентов на проверку тестом простоты, поскольку по сравнению с факторизацией, это процесс значительно более продолжительный.
Тесты простоты бывают такие:
- LL - тест простоты Люка-Лемера. Однозначно доказывает, является ли проверяемое число простым. Занимает, в зависимости от производительности процессора и величины экспоненты, от нескольких суток до месяцев.
- LL-D - повторная проверка ранее проверенных LL-тестом экспонент. Необходима для исключения ошибок и подтверждения корректности первого результата.
- PRP - вероятностный тест простоты Миллера-Рабина. Позволяет с высокой точностью определить, является ли число простым. Выполняется быстрее LL, но в случае положительного результата, разумеется, придётся выполнять проверку с помощью LL
Факторизация тоже бывает разная:
- TF - перебор делителей. Наименее производительный тест, перебирающий все возможные делители в определённом диапазоне. По понятным причинам, используется для поиска только небольших делителей, после чего заменяется на другие, более производительные алгоритмы. Нюанс состоит в том, что TF отлично распараллеливается, а значит - подходит для запуска на GPU, где общая скорость перебора увеличивается на два порядка по сравнению с обычными процессорами.
- PM1 - факторизация Р-1 методом Полларда. В отличие от перебора, находит (иногда) здоровенные делители, но за более продолжительное время. Состоит из двух фаз, вторая из которых требует достаточно большого объёма оперативной памяти.
- ECM - факторизация с помощью эллиптических кривых. Как и P-1, не гарантирует результат, но выполняется быстро и также находит большие делители. Тоже требует довольно много памяти.
Продолжение следует, кто дослушал - молодец, вот вам котик:
