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

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

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

к.т.н.

МГУ, 1972

пенсионер

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


Abstract:
This article defines a heuristic algorithm, the operating time of which is comparable to the time of the Luc-Lemer test when determining the simplicity of Mersenne numbers. The resulting heuristic algorithm determines the simplicity of numbers located in some neighborhood of Mersenne numbers.


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

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


УДК 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




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

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


 
 

Вверх