Факторы числа Мерсенны
Число Мерсенна - это число в виде 2 P -1.
Если P является простым, число Мерсенна может быть простым числом Мерсенна
(если P не является простым, число Мерсенна также не является простым).
При поиске простых чисел Мерсенна выгодно исключить экспоненты путем нахождения небольшого коэффициента перед началом потенциально длительного теста Lucas-Lehmer .
Существуют очень эффективные алгоритмы для определения того, делит ли число 2 P -1 (или, что то же самое, если 2 P mod (число) = 1).
Некоторые языки уже имеют встроенные реализации этой операции экспонента и мода (называемые modPow или аналогичные).
Ниже описано, как реализовать этот modPow самостоятельно:
Например, давайте вычислим 2 23 mod 47.
Преобразуйте экспонента 23 в двоичный код, вы получите 10111. Начиная с квадрата = 1, многократно меняйте его.
Удалите верхний бит экспоненты, и если это 1 умножить квадрат на основание экспоненции (2), тогда вычислите квадрат по модулю 47.
Используйте результат модуляции с последнего шага в качестве начального значения квадрата на следующем шаге:
Удалить необязательный
квадратный верхний бит умножается на 2 mod 47
------------ ------- ------------- ------
1 * 1 = 1 1 0111 1 * 2 = 2 2
2 * 2 = 4 0 111 нет 4
4 * 4 = 16 1 11 16 * 2 = 32 32
32 * 32 = 1024 1 1 1024 * 2 = 2048 27
27 * 27 = 729 1 729 * 2 = 1458 1
Так как 2 23 mod 47 = 1, 47 является фактором 2 P -1.
(Чтобы увидеть это, вычтите 1 с обеих сторон: 2 23 -1 = 0 mod 47.)
Поскольку мы показали, что 47 является фактором, 2 23 -1 не является простым.
Дальнейшие свойства чисел Мерсенна позволяют нам еще больше усовершенствовать процесс.
Любой фактор q из 2 P -1 должен иметь вид 2kP + 1, k - положительное целое число или ноль. Кроме того, q должно быть 1 или 7 mod 8.
Наконец, любой потенциальный фактор q должен быть простым .
Как и в других алгоритмах пробного деления, алгоритм останавливается, когда 2kP + 1> sqrt (N).
Эти тесты на примитивность работают только на числа Мерсенна, где P является простым. Например, M 4 = 15 не дает никаких факторов, использующих эти методы, но факторы в 3 и 5, ни один из которых не соответствует 2kP + 1.
Задача:
Используя приведенный выше метод, найдите коэффициент 2 929 -1 (ака M929)
Задачи, связанные с данной темой: подсчет в факторах простых коэффициентов декомпозиции целочисленного сита примитивности Эратосфена методом пробного деления пробного факторинга числа чисел Мерсенна - целое число X в N простых порядков простых чисел с помощью Trial Division Computers в 1948 году: 2¹²⁷-1
Using the above method find a factor of 2929-1 (aka M929)