Публикация научных статей.
Вход на сайт
E-mail:
Пароль:
Запомнить
Регистрация/
Забыли пароль?
Научные направления
Поделиться:
Разделы: Математика
Размещена 07.11.2019. Последняя правка: 11.11.2019.
Просмотров - 141

Самый быстрый алгоритм для определения простых чисел Мерсенна и для определения простых чисел в окрестности чисел Мерсенна

Усов Геннадий Григорьевич

к.т.н.

МГУ, 1972

пенсионер

Аннотация:
Полученный в статье эвристический алгоритм работает несколько быстрее известного теста Люка-Лемера при определении простоты чисел Мерсенна. Данный эвристический алгоритм определяет простоту чисел, расположенных в некоторой окрестности чисел Мерсенна.


Abstract:
The heuristic algorithm obtained in article works somewhat faster than the well-known Luc-Lemer test in determining the simplicity of Mersenne numbers. This heuristic algorithm determines the simplicity of numbers located in some neighborhood of Mersenne numbers.


Ключевые слова:
эвристический алгоритм; простое число; тест простоты; число Мерсенна

Keywords:
algorithm; Prime number; simplicity test; Mersenne number


УДК 511

Введение

Одной из задач современной математики является задача поиска максимальных простых чисел.

В настоящее время, самыми большими обнаруженными простыми числами являются простые числа Мерсенна. И этому способствует наличие удобного и быстрого критерия простоты в виде теста Люка-Лемера.

Автором был разработан эвристический алгоритм для определения простых чисел Мерсенна. Причем, тестовые расчеты на ЭВМ показали для этих двух тестов простоты схожие скорости определения простых чисел.

Теперь ставится задача о доработке эвристического алгоритма с целью улучшения его быстродействия работы по сравнению с быстродействием работы теста Люка–Лемера.

Актуальность

В настоящее время существует некоторый предел по определению простых чисел Мерсенна с применением теста Люка-Лемера с учетом существующих ЭВМ. Последнее найденное простое число Мерсенна 2^82589933-1.

Поэтому ставится задача найти тест простоты, который будет иметь лучшее быстродействие по сравнению с быстродействием теста Люка-Лемера при определении простых чисел Мерсенна, а также иметь возможность определять простоту чисел, отличных от чисел Мерсенна в некоторой окрестности.

Цели и задачи

Тест Люка-Лемера определяет для числа Мерсенна вида Mn = 2^n - 1 последовательность  (n – 1) чисел [1]:

S(1) = 4

S(i) = (S (i - 1)*S(i - 1) – 2) mod (Mn), 2 <= i <= n - 1

После определения последовательности чисел проверяется число S(n – 1).

Если это число равно 0, то число Mn будет простым числом.

Эвристический алгоритм для определения простых чисел Мерсенна имеет следующий вид[2]:

пусть n – натуральное число.

Число Мерсенна Mn = 2^n – 1 будет простым тогда и только тогда, когда выполняется условие:

a^d =  (Mn – 1) (mod Mn), где:

d – нечётное число, равное (Mn  - 1)/2;

a = 3.

Ставится задача преобразовать выражение 3^d в последовательность операций, аналогичных тесту Люка-Лемера.

 

Выражение 3^d представляет собой произведение d чисел 3, где d – нечётное число.

Чтобы удобнее работать с данными числами при определении их произведения по  (mod Mn), необходимо эти числа разложить попарно на блоки вида 3^d.

Однако удобнее раскладывать выражение 3^d попарно на блоки тогда, когда это выражение имеет чётное количество начальных блоков. Поэтому при раскладывании на блоки рассматривается следующее выражение:

3* 3^d= 3^(d+1) = 3^(Mn/2) = 3^d1, где d1 = Mn/2 = M(n-1)

Блок 3^d1  состоит из двух блоков:

3^d1  =  3^d2   * 3^d2, где d2 = d1 /2 =Mn/4 = M(n-2).

Блок 3^d2 состоит из двух блоков:

3^d2   = 3^d3   * 3^d3, где d3 = d2 /2 =Mn/8 = M(n-3).

Блок 3^d3 состоит из двух блоков:

3^d3   = 3^d4   * 3^d4, где d4 = d3/2 = Mn/16= M(n-4)

Данные разложения можно продолжить до тех пор, пока не будут определены блоки вида 3^1.

Теперь можно построить последовательность чисел, аналогичную последовательности чисел для теста Люка-Лемера. В этом случае получается последовательность из (n – 1) чисел:

В(1) = 9

B(i) = (B (i - 1) * B(i - 1)) mod (Mn), 2 <= i <= n – 1.

Поскольку вместо числа 3^d теперь в алгоритме будет число 3^(d+1), то меняется основное условие эвристического алгоритма для определения простоты числа:

3^d * 3 =  (Mn – 1)*3 (mod Mn), или

3^(Mn/2) = (Mn – 3) (mod Mn), или

3^M(n-1) = (Mn – 3) (mod Mn).

Тогда условие для определения простых чисел Мерсенна с помощью эвристического алгоритма будет выглядеть следующим образом:

Пусть n –  нечётное число.

Число Мерсенна Mn = 2^n – 1 будет простым тогда и только тогда, когда (n – 1) член последовательности:

В(1) = 9

B(i) = (B (i - 1)*B(i - 1)) mod (Mn), 2 <= i <= n - 1

будет равен числу (Mn – 3):

B(n-1) = (Mn – 3).

 

В результате получился эвристический алгоритм, похожий на алгоритм теста Люка-Лемера, а отличающийся тем, что в эвристическом алгоритме отсутствует операция вычитания числа 2 на каждом шаге.

Проведённые тестовые расчёты на ЭВМ показали, что эвристический алгоритм определяет простые числа Мерсенна в среднем на 2% быстрее, чем определяет простые числа тест Люка-Лемера.

То есть, получен самый быстрый эвристический алгоритм для определения простых чисел Мерсенна.

 

Данный эвристический алгоритм можно ещё немного упростить.

Можно в виде первоначального числа В(1) назначать числа вида

3^(2^(p)), где 0 <= p <= P.

Тогда количество элементов в последовательности чисел уменьшается на р. При этом немного уменьшается время работы алгоритма за счёт того, что не проводится несколько операций по mod (Mn) и операций сопровождения цикла для небольших чисел.

Кроме того, если рассматриваются несколько чисел Мерсенна, то уже посчитанное начальное число можно будет применить при проверке следующего числа.

Начальное число для каждого определяемого числа определяется как число 3^(2^(p)), немного большее, чем число Mn.

 

Следующим этапом исследований является применение полученного эвристического алгоритма для определения простых чисел в окрестности чисел Мерсенна.

Последовательности чисел Mnk в окрестности чисел Мерсенна можно определить следующим образом:

Mnk = 2^n – 1+k, где n – целое число, k – целое число, кратное 2.

Поскольку появляются числа Mnk, то в целях единого обозначения можно числа Мерсенна Mn обозначать в виде Mn0.

Если число k отрицательное, например, k = -4, то последовательность чисел в окрестности чисел Мерсенна будет иметь вид Mn(-4).

Если имеется число Mnk, то эвристический алгоритм из [2], если определить а = 3, будет выглядеть следующим образом :

3^((Mnk-1)/2) =  D (mod Mnk), где

D = Mnk – 1 или D = 1.

 

Рассмотрим случай, когда число k – положительное.

Подставим в это уравнение значение Mnk:

3^((2^n – 1+k -1)/2) =  D (mod Mnk), или

3^((2^n – 2)/2)* 3^(k /2) =  D (mod Mnk), или

3^(2^(n –1)- 1) (mod Mnk) * 3^(k /2) (mod Mnk) =  D (mod Mnk), или

3^M(n-1) (mod Mnk) * 3^((k /2)-1) (mod Mnk) =  D (mod Mnk).

В результате получается эвристический алгоритм для определения простых чисел Mnk в окрестности чисел Мерсенна (для числа k – положительного, кратного 2) в виде следующих шагов:

шаг 1.  определяется значение эвристического алгоритма для простых чисел Мерсенна по модулю Mnk,

            А = 3^M(n-1) (mod Mnk)

шаг 2. определяется произведение числа А на значение произведения ( k/2-1) оснований степени 3 по модулю Mnk,

            В = (А * 3^((k /2)-1)) (mod Mnk)

шаг 3. полученное произведение В сравниваются с величиной D:

            Если имеет место равенство B = D, то число Mnk – простое.

 

Рассмотрим случай, когда число k – отрицательное.

Подставим в это уравнение значение Mnk:

3^((2^n – 1+k -1)/2) =  D (mod Mnk), или

3^((2^n – 2)/2)* 3^(k /2) =  D (mod Mnk), или

3^(2^(n –1)-1) (mod Mnk) =  D (mod Mnk) * 3^(- k /2) (mod Mnk), или

3^M(n-1) (mod Mnk) =  (D * 3^(1-k /2)) (mod Mnk)

В результате получается эвристический алгоритм для определения простых чисел Mnk в окрестности чисел Мерсенна (для числа k – отрицательного, кратного 2) в виде следующих шагов:

шаг 1.  определяется значение эвристического алгоритма для простых чисел Мерсенна по модулю Mnk,

            А = 3^M(n-1) (mod Mnk)

шаг 2. определяется произведение числа D на значение произведения (1 - k/2) оснований степени 3 по модулю Mnk,

            С = (D * 3^(1-k /2)) (mod Mnk)

шаг 3. полученное число А сравнивается с полученным числом С:

            Если имеет место равенство А = С, то число Mnk – простое.

В обоих случаях числа k происходят вычисления и сравнение для двух вариантов числа D.

Таким образом, получен эвристический алгоритм для определения простоты чисел, расположенных в окрестности чисел Мерсенна с шагом 2.

       

В работе [3] был рассмотрен тест Пепена, который определил необходимое и достаточное условие для определения простоты чисел вида Fk = 2^(2^k)+1 (числа Ферма):

при k >= 1 число Fk является простым тогда и только тогда, когда:

3^((Fk – 1 )/2) = Fk-1 (mod Fk).

Следовательно, данный тест для определения простых чисел Ферма, а также определения простых чисел вида 2^k+1, подтверждает верность формулы эвристического алгоритма для определения простых чисел в окрестности чисел Мерсенна.

 

Дальнейшие исследования позволили обозначить возможную область простых чисел, расположенных рядом с числами Мерсенна, которые может определять эвристический алгоритм.

Для каждого значения n был проведён перебор нечётных чисел, больших Mn. В результате первые составные числа, которые эвристический алгоритм определяет как простые, расположены на следующих расстояниях от Mn (при этом были определены простые числа: представлено их количество):

для  n = 7 расстояние  572 найдено простых чисел 95

для  n = 8 расстояние  444 найдено простых чисел 71

для  n = 9 расстояние  188 найдено простых чисел 29

для  n = 10 расстояние  514 найдено простых чисел 70

для  n = 11 расстояние  414 найдено простых чисел 55

для  n = 12 расстояние  862 найдено простых чисел 99

для  n = 13 расстояние  206 найдено простых чисел 23

для  n = 14 расстояние  144 найдено простых чисел 14

для  n = 15 расстояние  8270 найдено простых чисел 784

для  n = 16 расстояние  6502 найдено простых чисел 587

для  n = 17 расстояние  7406 найдено простых чисел 632

для  n = 18 расстояние  16074 найдено простых чисел 1296

для  n = 19 расстояние  6590 найдено простых чисел 508

для  n = 20 расстояние  2406 найдено простых чисел 170

для  n = 21 расстояние  16766 найдено простых чисел 1156

для  n = 22 расстояние  58074 найдено простых чисел 3799

для  n = 23 расстояние  17246 найдено простых чисел 1078

для  n = 24 расстояние  1662 найдено простых чисел 91

для  n = 25 расстояние  194 найдено простых чисел 10

для  n = 26 расстояние  25674 найдено простых чисел 1401

для  n = 27 расстояние  559490 найдено простых чисел 29966

для  n = 28 расстояние  70092 найдено простых чисел 3639

Назовём эти расстояния рабочим диапазоном для применения эвристического алгоритма.

Для чисел n, равных от 29 до 35, рабочий диапазон будет больше 600000, при этом было определено более 28000 простых чисел на каждом рабочем диапазоне.

При этом было замечено, что для чисел Mnk = Mn + 4*t, t> 0 рабочий диапазон будет намного больше, чем для чисел Mnk = Mn + 2 + 4*t, t> 0.

Аналогичная картина получается для определения рабочего диапазона для числа Mn в том случае, когда число k будет отрицательным.

Поэтому при определении больших простых чисел можно говорить о больших рабочих диапазонах больше числа Mn (или меньше числа Mn), в которых можно применить эвристический алгоритм для определения простых чисел Мерсенна.

Научная новизна

В результате проведённых исследований был получен эвристический алгоритм определения простых чисел Мерсенна, имеющий лучшее быстродействие работы по сравнению с быстродействием работы теста Люка-Лемера.

Полученный эвристический алгоритм позволяет определять простоту большого количества чисел, расположенных в окрестности чисел Мерсеннав в рамках рабочего диапазона.

Библиографический список:

1.Василенко О. Н. Теоретико-числовые алгоритмы в криптографии, М.:МЦНМО, 2003- 328 c.
2. Усов Г.Г., Эвристический алгоритм определения простых чисел с применением формул Миллера-Рабина. Электронный периодический рецензируемый научный журнал «SCI-ARTICLE.RU», №73 (сентябрь) 2019, стр. 71-75. http://sci-article.ru/number/09_
3. Крэндалл Р., Померанс К. Простые числа: Криптографические и вычислительные аспекты. Пер. с англ. / Под ред. и с предисл. В. Н. Чубарикова. - М.: УРСС: Книжный дом




Комментарии пользователей:

11.11.2019, 7:25 Усов Геннадий Григорьевич
Отзыв: В результате исследований была немного доработана статья. Числа в окрестности числа Mn рассматриваются не с шагом 4, а с шагом 2. Проведена оценка рабочих диапазонов для малых чисел Mn, где с помощью эвристического алгоритма определяются только простые числа. Немного отредактирована новизна работы и расширен библиографический список.


Оставить комментарий


 
 

Вверх