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

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

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

к.т.н.

МГУ, 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]. Причем, тестовые расчеты на ЭВМ показали для этих двух тестов простоты схожие скорости определения простых чисел.

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

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

В настоящее время существует некоторый предел по определению простых чисел Мерсенна с применением теста Люка-Лемера с учетом существующих ЭВМ. Последнее найденное простое число Мерсенна 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.  определяется значение эвристического алгоритма для простых чисел Мерсенна по (mod Mnk),

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

шаг 2. определяется произведение числа А на значение произведения ( k/2-1) оснований степени 3 по (mod 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.  определяется значение эвристического алгоритма для простых чисел Мерсенна по (mod Mnk),

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

шаг 2. определяется произведение числа D на значение произведения (1 - k/2) оснований степени 3 по (mod 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

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

Для чисел 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», №74 (октябрь) 2019, стр. 22-26. http://sci-article.ru/number/10_2019.pdf
3. Крэндалл Р., Померанс К. Простые числа: Криптографические и вычислительные аспекты. Пер. с англ. / Под ред. и с предисл. В. Н. Чубарикова. - М.: УРСС: Книжный дом




Рецензии:

18.01.2020, 12:18 Мирмович Эдуард Григорьевич
Рецензия: Автор продолжил работу в избранной области, хотя не очень понятно, почему он её не публикует в каких-то математических журналах типа "Квант". Желательно хотя бы в некоторых формулах приводить ниже по два-три конкретных примера как инструмент для представления читателем, что даёт каждая формула, привести хоть несколько оценок сравнения времени расчёта трёх моделей реализации предыдущих и предлагаемого эвристических алгоритмов. Однако автор сам выбирает и идейное наполнение своей работы, и контент. Надо расставить пробелы, где их нет (Word подскажет). Несмотря на то, что актуальность статья для рецензента под большим вопросом, преданность автора поиску упрощений в нахождении больших простых чисел и его компетентность в этой области дают рецензенту возможность рекомендовать эту работу к публикации после прииятия им решения - учитывать предложения рецензента или не учитывать.

19.01.2020 13:13 Ответ на рецензию автора Усов Геннадий Григорьевич:
Уважаемый Эдуард Григорьевич! Благодарю Вас за рецензию к моей статье. Если я публикуюсь в данном журнале, то, наверное, надо продолжать отдавать интересные материалы этому журналу. Эвристический алгоритм похож на алгоритм Люка-Лемера и отличается от него на 3 числа. В расчетах по этим алгоритмам для чисел Мерсенна на печать выходят одни и те же простые числа. Поэтому я не приводил примеров определения простых чисел Мерсенна с помощью эвристического алгоритма. Однако, когда я рассматривал числа в окрестности чисел Мерсенна, то привел результаты расчетов в виде количества определяемых простых чисел. Пробелы расставил. Спасибо за подсказку! А актуальность работы в том, что найден более быстрый алгоритм определения простых чисел Мерсенна. И пусть всего на чуть-чуть по времени.



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

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


6.12.2019, 16:55 Усов Геннадий Григорьевич
Отзыв: В результате исследований была немного доработана статья. Добавлен 3-ий пункт научной новизны. В связи с публикацией представлена статья [2].


19.01.2020, 15:30 Мирмович Эдуард Григорьевич
Отзыв: Физическая миссия простых чисел не изучена, и нет уверенных надежд, что (кроме криптографии) этому будут посвящены серьёзные исследования в микро- и макрофизике. Даже в теории групп и представлений неприводимым многочленам (математическое обобщение простых чисел) уделено фундаментальное место, а простым числам - нет. Нет исследований и простых чисел в других, не десятичной, системах счисления. Успехов автору в его деятельности на пенсии. Справиться с текучкой и посвятить время для любимых занятий дорогого стоят.


19.01.2020, 16:55 Усов Геннадий Григорьевич
Отзыв: Спасибо за напутствие! Сейчас много свободного времени, и есть желание решать интересные задачи, на которые ранее не обращал внимание.


20.01.2020, 3:13 Мирмович Эдуард Григорьевич
Отзыв: Максимальное число электронов конечных элементов групп: n = 2, 8, 8, 18, 18, 32, 32... Всегда ли n - 1 - простое число? Решением каких диофантовых уравнений являются простые числа?Простые числа и фрактальная концепция. Стабильное состояние любого объекта должно быть гомеоморфным некому простому числу (хотелось бы). Устойчивость и простые числа (в приципе). Посмотрите адиковые числа. В общем, дерзайте.


20.01.2020, 13:08 Усов Геннадий Григорьевич
Отзыв: Уважаемый Эдуард Григорьевич! Спасибо Вам за перечень интересных тем по решения задач с применением простых чисел. В настоящее время я пробую варианты по факторизации чисел. В дальнейшем предполагаю заняться решением одной из задач, предложенных Вами. Если Вы не против, я попробую обратиться к Вам за разъяснениями по этой задаче по Вашей электронной почте, которая указана в настоящем журнале.


3.02.2020, 16:54 Ремизов Вадим Григорьевич
Отзыв: Уважаемый Геннадий Григорьевич! Скажите пожалуйста, какое самое большое простое число Мерсенна было Вами установлено с помощью самого быстрого алгоритма для определения простых чисел Мерсенна? С уважением Ремизов Вадим Григорьевич


3.02.2020, 19:26 Усов Геннадий Григорьевич
Отзыв: Уважаемый Вадим Григорьевич! Задачей статьи был не поиск самого большого простого числа Мерсенна, а поиск быстрого алгоритма для такого поиска. На своем домашнем компьютере я определял простое число Мерсенна М-23209 с целью проверки алгоритма в разумное время - несколько часов. Очередные простые числа Мерсенна не имеет смысла искать на домашнем компьютере: самое большое простое число не определишь из-за нехватки времени рабочего состояния компьютера, а меньшие числа - уже известны. С уважением, Усов Геннадий Григорьевич


5.02.2020, 19:00 Ремизов Вадим Григорьевич
Отзыв: Уважаемый Геннадий Григорьевич! Не могли бы пояснить, как Вы записываете простые числа в окрестности чисел Мерсенна.


5.02.2020, 20:14 Усов Геннадий Григорьевич
Отзыв: Уважаемый Вадим Григорьевич! Числа Мерсенна имеют вид Mn = 2^n - 1, где n – целое число. Числа в окрестности чисел Мерсенна определяются следующим образом: Mnk = 2^n – 1 + k, где n – целое число, k – целое число, кратное 2. Некоторое количество чисел в окрестности чисел Мерсенна являются простыми числами.


6.02.2020, 14:42 Ремизов Вадим Григорьевич
Отзыв: Уважаемый Геннадий Григорьевич! И последний вопрос. С помощью какого теста производится проверка простоты чисел в окрестности чисел Мерсенна?


6.02.2020, 18:28 Усов Геннадий Григорьевич
Отзыв: Уважаемый Вадим Григорьевич! Согласно определению: "эвристический алгоритм (эвристика) — алгоритм решения задачи, включающий практический метод, не являющийся гарантированно точным или оптимальным, но достаточный для решения поставленной задачи". Простота чисел в окрестности чисел Мерсенна была проверена на небольших значениях n и k с помощью простого перебора делителей. Результаты этих расчетов были представлены в статье. Следовательно, данный эвристический алгоритм можно распространить на большие значения числа n.


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


 
 

Вверх