Как работает проект GIMPS, который позволяет находить новые простые числа?

Проект GIMPS (Great Internet Mersenne Prime Search) позволяет находить новые простые числа Мерсенна. ru.wikipedia.org 3dnews.ru С технической точки зрения он представляет собой базу данных с информацией об экспонентах чисел Мерсенна и HTTP API, которое даёт возможность получить задание на определённую операцию с одной из этих экспонент и вернуть результат. habr.com

При проверке каждой экспоненты обычно придерживаются определённой последовательности действий: habr.com

1. Trial Factoring (TF) — перебор делителей, проверка, не делится ли кандидат на все подряд простые числа до определённого размера в битах. habr.com
2. Факторизация методом Полларда (P-1). habr.com В отличие от перебора, иногда находит большие делители, но требует значительного объёма оперативной памяти. habr.com
3. Вероятностный тест простоты Миллера-Рабина (PRP). habr.com Это полноценная проверка на простоту, которая с абсолютной точностью определяет составные числа и с очень высокой — простые. habr.com
4. Сертификация PRP (CERT) с помощью Verifiable Delay Function. habr.com Проверка результата теста на простоту, которая подтверждает, что присланный результат корректен и действительно вычислен, а не выдуман. habr.com

После прохождения всех этих этапов экспонента считается обработанной и проверенной. habr.com

Ежедневно проект GIMPS получает результаты вычислений сотен участников. ru.wikipedia.org По каждому из них проект ведёт статистику, публикует и регулярно обновляет рейтинги производительности и результативности. ru.wikipedia.org Для усиления соревновательного эффекта в проекте реализована возможность объединения участников в команды. ru.wikipedia.org

Пользователь

Время добавления