--- title: 'числа Мерсенна на пальцах, ч. 2' url: 'https://ky0uraku.xyz/blog/20180109-chisla-mersenna-na-paltsah-2' markdown: 'https://ky0uraku.xyz/blog/20180109-chisla-mersenna-na-paltsah-2.md' date: '2018-01-09' description: 'Итак, с лирическим отступлением покончено, пришло время разобраться, что, собственно, вообще происходит? Жил-был во Франции математик Мерсенн, довольно крутой дядька, много чего сделавший в своё время для науки. Нас в данном случае будет интересовать только одно направление его деятельности - изуче…' taxonomy: tag: - gimps - math category: - articles --- # числа Мерсенна на пальцах, ч. 2 [Тексты](https://ky0uraku.xyz/blog) / 9 января 2018 [gimps](https://ky0uraku.xyz/blog/tag:gimps) [math](https://ky0uraku.xyz/blog/tag:math) Итак, с лирическим отступлением покончено, пришло время разобраться, что, собственно, вообще происходит? Жил-был во Франции математик [Мерсенн](https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%80%D1%81%D0%B5%D0%BD%D0%BD,_%D0%9C%D0%B0%D1%80%D0%B5%D0%BD), довольно крутой дядька, много чего сделавший в своё время для науки. Нас в данном случае будет интересовать только одно направление его деятельности - изучение свойств чисел, представляющих собой степени двойки минус единица. Было замечено, что некоторые из этих чисел простые, причём в каждом случае экспонента, то есть степень, в которую возводится двойка, при этом тоже представляла собой простое число. Первые простые числа Мерсенна были найдены давным-давно, ещё вручную. Ф вот потом, когда количество цифр в ПЧМ перевалило за сотню, разумеется, стало понятно, что без ЭВМ не обойтись. К счастью, в 1878 году был разработан полиномиальный тест простоты, применимый именно для таких чисел, который настолько превосходил по скорости все другие, что вот уже долгое время звание [самых больших](https://ru.wikipedia.org/wiki/%D0%9D%D0%B0%D0%B8%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%B5%D0%B5_%D0%B8%D0%B7%D0%B2%D0%B5%D1%81%D1%82%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D0%BE%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%BE) известных человечеству простых чисел удерживают простые числа Мерсенна. Переходя к практической части - проект распределённых вычислений [GIMPS](https://ru.wikipedia.org/wiki/GIMPS), который, собственно, уже третий десяток лет и занимается тем, что находит новые ПЧМ с помощью теста Люка-Лемера. Принцип работы следующий - волонтёры устанавливают на компьютер ПО, которое после первичной настройки автоматически получает задания с сервера проекта и отправляет туда результаты. Задания можно разделить на две основные группы - тесты простоты и факторизация. Первая - представляет собой, собственно, проверку на простоту очередного числа Мерсенна с простой экспонентой. Факторизация - это попытка разложить число Мерсенна на множители, то есть доказать обратное (что число - не простое, а составное). Делается это для того, чтобы заранее сократить число претендентов на проверку тестом простоты, поскольку по сравнению с факторизацией, это процесс значительно более продолжительный. Тесты простоты бывают такие: - LL - тест простоты [Люка-Лемера](https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D1%81%D1%82_%D0%9B%D1%8E%D0%BA%D0%B0_%E2%80%94_%D0%9B%D0%B5%D0%BC%D0%B5%D1%80%D0%B0). Однозначно доказывает, является ли проверяемое число простым. Занимает, в зависимости от производительности процессора и величины экспоненты, от нескольких суток до месяцев. - LL-D - повторная проверка ранее проверенных LL-тестом экспонент. Необходима для исключения ошибок и подтверждения корректности первого результата. - PRP - вероятностный тест простоты [Миллера-Рабина](https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D1%81%D1%82_%D0%9C%D0%B8%D0%BB%D0%BB%D0%B5%D1%80%D0%B0_%E2%80%94_%D0%A0%D0%B0%D0%B1%D0%B8%D0%BD%D0%B0). Позволяет с высокой точностью определить, является ли число простым. Выполняется быстрее LL, но в случае положительного результата, разумеется, придётся выполнять проверку с помощью LL Факторизация тоже бывает разная: - TF - [перебор делителей](https://ru.wikipedia.org/wiki/%D0%9F%D0%B5%D1%80%D0%B5%D0%B1%D0%BE%D1%80_%D0%B4%D0%B5%D0%BB%D0%B8%D1%82%D0%B5%D0%BB%D0%B5%D0%B9). Наименее производительный тест, перебирающий все возможные делители в определённом диапазоне. По понятным причинам, используется для поиска только небольших делителей, после чего заменяется на другие, более производительные алгоритмы. Нюанс состоит в том, что TF отлично распараллеливается, а значит - подходит для запуска на GPU, где общая скорость перебора увеличивается на два порядка по сравнению с обычными процессорами. - PM1 - факторизация [Р-1 методом Полларда](https://ru.wikipedia.org/wiki/P-1_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4_%D0%9F%D0%BE%D0%BB%D0%BB%D0%B0%D1%80%D0%B4%D0%B0). В отличие от перебора, находит (иногда) здоровенные делители, но за более продолжительное время. Состоит из двух фаз, вторая из которых требует достаточно большого объёма оперативной памяти. - ECM - факторизация с помощью [эллиптических кривых](https://ru.wikipedia.org/wiki/%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D1%81_%D0%BF%D0%BE%D0%BC%D0%BE%D1%89%D1%8C%D1%8E_%D1%8D%D0%BB%D0%BB%D0%B8%D0%BF%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D1%85_%D0%BA%D1%80%D0%B8%D0%B2%D1%8B%D1%85). Как и P-1, не гарантирует результат, но выполняется быстро и также находит большие делители. Тоже требует довольно много памяти. Продолжение следует, кто дослушал - молодец, вот вам котик: [![](https://ky0uraku.xyz/blog/20180109-chisla-mersenna-na-paltsah-2/11-1k.webp)](https://ky0uraku.xyz/blog/20180109-chisla-mersenna-na-paltsah-2/11.webp) --- ## Navigation - Parent: [Последние тексты](https://ky0uraku.xyz/blog.md) - Previous: [числа Мерсенна на пальцах, ч. 3](https://ky0uraku.xyz/blog/20180119-chisla-mersenna-na-paltsah-3.md) - Next: [числа Мерсенна на пальцах, ч. 1](https://ky0uraku.xyz/blog/20180107-chisla-mersenna-na-paltsah-1.md)