Статья опубликована в №74 (октябрь) 2019
Разделы: Математика
Размещена 26.09.2019. Последняя правка: 04.11.2019.
Просмотров - 1381

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

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

к.т.н.

МГУ, 1972

пенсионер

УДК 511

Введение

Как известно, самыми большими известными простыми числами являются простые числа Мерсенна.

Числа Мерсенна образуют последовательность чисел вида:

Mn = 2^n – 1, где n – натуральное число.

Самое большое известное простое число – 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 простое.

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

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

Ставится задача: найти алгоритм определения простоты числа для очень больших чисел, время работы которого сравнимо со временем работы  теста Люка-Лемера.

 

В работе [2] был рассмотрен эвристический алгоритм определения простых чисел с применением формул Миллера-Рабина. Данный алгоритм позволяет отказаться от вероятностных способов поиска псевдопростых чисел и определять простые числа алгоритмическим методом.

Исследования последовательности чисел Мерсенна Mn = 2^n – 1 показали, что число d = (Mn – 1) / 2 будет всегда нечётным числом.

Следовательно, для проверки на простоту чисел Mn, у которых число d является нечётным числом, можно применить упрощённую версию эвристического алгоритма:

пусть Mn— нечётное число, большее 1, и число  Mn - 1  однозначно представляется в виде

Mn – 1 = 2 * d, где  d -  нечётное число.

Тогда для этого числа Mn выбирается последовательность чисел a от 2 до некоторого числа A.

Для каждого числа a из этой последовательности определяются числа  на основании формулы

P = a^(d) (mod Mn)

Если для всех чисел Р  расчеты по модулю n равны либо 1, либо (Mn – 1), то число Mn будет простым числом.

На следующем этапе поиска алгоритма был проведен анализ остатков по модулю для небольших чисел Мерсенна при применении упрощённой версии эвристического алгоритма для различных оснований степени a. Данный анализ показал, что для простых чисел Мерсенна эти остатки по модулю состоят только из числа 1 или из числа (Mn – 1).

Поэтому необходимо разработать алгоритм поиска последовательностей, состоящих из 1 и (Mn – 1).

Для уточнения вида алгоритма были проведены исследования при различных значениях оснований степени: числа a.

Проведённые исследования показали, что при основании степени a = 3 остатки по модулю для небольших простых чисел Мерсенна равны числу  (Mn – 1), т.е. имеет место только один раунд определения остатков по модулю, а это означает, что получена формула в виде однократного применения эвристического алгоритма для одного числа с целью определения простых чисел Мерсенна.

Проведённые исследования с числами Мерсенна Mn для n < 20000 показали, что эвристический  алгоритм определяет все простые числа Мерсенна на этом интервале. При этом другие числа Мерсенна не определяются, как простые числа.

Аналогичные результаты можно получить для основания степени 6, 12. И таких значений оснований степени будет много. А для основания степени 9 все остатки по модулю равны 1. И таких оснований степени будет так же много.

Однако наиболее удобно выбрать основание степени a = 3.

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

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

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

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

a = 3.

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

Проведённые исследования на числах Мерсенна, меньших 2^20000-1, показали, что скорость работы нового эвристического алгоритма почти равна скорости работы алгоритма Люка-Лемера.

Получается, что время определения (n-2) квадратов чисел, меньших n, в виде остатков по модулю n, сравнимо по времени со временем определения остатка по модулю n для числа a^((n-1)/2).

Теперь можно рассмотреть вопросы определения простоты чисел, расположенных в окрестности чисел Мерсенна.

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

Mn4 = 2^n – 1+4, где n – натуральное число.

То есть, рассматриваем числа, расположенные в окрестности чисел Мерсенна.

Значения числа n для простых чисел Mn4 на диапазоне

n, 1< n < 3000, 

образуют следующую последовательность чисел:

2, 3, 4, 6, 7, 12, 15, 16, 18, 28, 30, 55, 67, 84, 228, 390, 784, 1110, 1704, 2008, 2139, 2191, 2367, 2370.

Аналогичным образом можно найти множество других последовательностей

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

отличающихся от чисел Мерсенна Mn на числа k, кратные 4.

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

Были проведены расчеты для некоторых чисел k с применением эвристического алгоритма определения простоты чисел Мерсенна.

В результате получились следующие результаты.

Значения числа n для простых чисел Mn8 на диапазоне n от 1 до 3000 образуют следующую последовательность чисел:

2, 4, 6, 8, 10, 16, 18, 20, 28, 30, 38, 44, 78, 88, 98, 126, 160, 174, 204, 214, 588, 610, 798, 926, 1190, 1198, 1806, 1888, 2648.

Значения числа n для простых чисел Mn12 на диапазоне n от 1 до 3000 образуют следующую последовательность чисел:

3, 5, 7, 9, 15, 23, 29, 31, 55, 71, 77, 297, 573, 1301, 1555, 1661.

Значения числа n для простых чисел Mn16 на диапазоне n от 1 до 3000 образуют следующую последовательность чисел:

2, 3, 4, 5, 6, 8, 10, 11, 12, 15, 16, 22, 23, 26, 30, 32, 40, 42, 46, 61, 72, 76, 155, 180, 198, 203, 310, 328, 342, 508, 510, 515, 546, 808,1563, 2772.

Значения числа n для простых чисел Mn20 на диапазоне n от 1 до 3000 образуют следующую последовательность чисел:

2, 6, 30, 162, 654, 714, 1370, 1662, 1722, 2810.

При этом начальные числа одних последовательностей Mnk могут совпадать с начальными числами других последовательностей чисел Mnk.

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

Тестовые проверки чисел Mnk на делители показали правильность эвристического алгоритма определения простоты чисел Мерсенна для определения простоты чисел Mnk в окрестности чисел Мерсенна. Тестовые проверки проводились для числа n, 1 <  n < 60, при значениях k, 4 =< k =< 100.

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

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

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

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

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

12.08.2021, 14:17 Цорин Борис Иосифович Отзыв: Проще говоря: автор поискал и не нашел сильно псевдопростых чисел по основанию 3 (то есть дающих ложноположительный результат при тесте Миллера-Рабина при a=3) с неотрицательной разностью в пределах 100 с числами Мерсенна. На основе своего неуспешного поиска автор сделал вывод, что таких чисел и нет вообще. Гражданин Усов, это называется не "эвристический алгоритм", а "гипотеза", и гипотеза весьма голословная: перебранное Вами множество чисел имеет мощность около 5300 (Вы проверили примерно 2300 чисел Мерсенна с простым n и 3000 чисел, близких к числам Мерсенна), а сильно псевдопростые числа по основанию 3, начиная с семизначных, встречаются в лучшем случае 30 на миллион, такой уровень проверки гипотезы хуже подбрасывания монетки: шанс случайно натолкнуться на число, опровергающее гипотезу, в лучшем случае около 15%. И что ж Вы не попробовали взять отрицательные k, раз используете термин "окрестность"? Уже при k=-6 и n=7 наткнулись бы на опровержение. Очень жаль, что статьи подобного качества оказываются опубликованными в, казалось бы, рецензируемом журнале. Уважаемая редколлегия, пожалуйста, тщательнее проверяйте статьи перед публикацией в журнале.

15.08.2021, 15:38 Цорин Борис Иосифович Отзыв: P.S. Простите великодушно, ошибся в прошлом отзыве, даже не 5300, а 3700, что делает выполненную "проверку гипотезы" еще менее полезной: во-первых, не 2300, а 2200 чисел Мерсенна (ведь простые числа Мерсенна и не могли стать контрпримером), а во-вторых, не 3000, а 1500 близких к ним чисел (не обратил сначала внимания, что автор скромно ограничился k, делящимися на 4). Так что шанс случайно наткнуться на опровержение гипотезы был порядка 9%. Вот если бы Вы проверили гипотезу хотя бы для миллиона чисел Мерсенна, и, соответственно, 25 миллионов чисел, которые Вы называете "в окрестности", тогда был бы смысл публиковать статью. Но, повторю, исключительно как гипотезу.

3.09.2021, 12:52 Усов Геннадий Григорьевич Отзыв: 1. "при k=-6" - пример неудачный. Шаг выбора числа k в статье - 4. 2. Идея статьи в следующем: если есть числа Mn = 2^n – 1, то почему не может быть чисел Mn4 = 2^n – 1 + 4? 3. Было замечено, что в районе (окрестности) числа Mn при больших n простые числа определяются с помощью одной проверки. 4. "Минус" ("при k=-6") в этой статье не обсуждался. 5. Алгоритм - это последовательность формул, которые позволяют придти к нужному результату при любых параметрах в рамках допущений (небольшая окрестность).

3.09.2021, 15:29 Цорин Борис Иосифович Отзыв: То, что Ваш алгоритм дает нужный результат при относительно небольших n, не гарантирует, что он даст нужный результат при любом n.

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