Публикация научных статей.
Вход на сайт
E-mail:
Пароль:
Запомнить
Регистрация/
Забыли пароль?
Вакпрофи. Публикация статей ВАК, Scopus
Научные направления
Поделиться:
Разделы: Математика
Размещена 26.09.2019.
Просмотров - 144

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

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

к.т.н.

МГУ, 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 – 2) остатков по модулю квадратов чисел, меньших n.  После того, как последовательность сформирована, оценивается последний элемент последовательности.

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

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

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

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

Чтобы разработать новый алгоритм, необходимо сначала изучить числа Мерсенна.

Исследования последовательности чисел Мерсенна показали, что при делении всех этих чисел на 2 получается нечётное число.

Поэтому при разработке нового алгоритма была применена формула первого условия теста Миллера-Рабина, который работает с комбинацией числа n и числа (n – 1)/2.

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

пусть  n  — нечётное число, большее 1, и число  (n – 1)  однозначно представляется в виде:

n – 1 = 2*d , где  d -  нечётно;

тогда целое число a, 1 < a < n, называется свидетелем простоты числа n, если выполняется условие:

 a^d = 1 (mod n)

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

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

Поэтому необходимо разработать алгоритм поиска последовательностей, состоящих из 1 и (n – 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.

 

Проведённые исследования на числах Мерсенна, меньших 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 – натуральное число, k - натуральное число, кратные 4,

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

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

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

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

Показатели n простых чисел Mn8 на диапазоне n, 1< n < 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< n < 3000, образуют следующую последовательность:

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

Показатели n простых чисел Mn16 на диапазоне n, 1< n < 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< n < 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.




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

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


 
 

Вверх