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

Эвристический алгоритм определения простых чисел с применением формул Миллера-Рабина

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

к.т.н.

МГУ, 1972

пенсионер

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


Abstract:
This article defines a heuristic algorithm that significantly speeds up the work of the Miller-Rabin test in determining the simplicity of a number.


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

Keywords:
heuristic algorithm; prime; simplicity test


УДК 511

Введение

С давних времён существует необходимость получения простых чисел. Таких чисел, у которых только два делителя: 1 и само число.

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

Первым алгоритмом было решето Эратосфена. Однако решето Эратосфена строится, начиная с числа 1, и чтобы определять большие простые числа необходимо затратить много времени.

Следующим алгоритмом стал тест Ферма (основанный на малой теореме Ферма, которая позже была доказана). Здесь Ферма заметил, что если определять остатки от деления числа, у которого степень есть  число (n – 1), на само число n, то для всех простых чисел этот остаток равен числу 1.

Однако, позднее было замечено, что тест Ферма не является достаточным: существуют составные числа (не простые числа), для которых выполняется тест  Ферма.

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

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

В большинстве существующих вероятностных тестах простоты используется большое количество раундов при определении простых чисел, после чего выносится заключение, что число n, при выполнении условий теста, будет вероятностно простым (псевдопростым). Для больших чисел количество раундов будет большим, например, для теста Миллера-Рабина количество раундов для числа  равно log(n).

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

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

Цели и задачи.

Во многих существующих тестах простоты используется уравнение теста Ферма, в котором, в качестве показателей степени, применяются различные величины, производные от исследуемого числа n.

Это связано с тем, что исследователи заметили, что при подстановке различных степеней для простого числа n в расчете по модулю n появляются значения, равные числам 1 или (n – 1).

Например, в тесте простоты Соловея-Штрассена немного изменена формула Ферма: вместо степени  (n – 1) применяется степень (n – 1)/2.

В вероятностном полиномиальном тесте простоты Миллера-Рабина пошли дальше: значение (n – 1) делится на 2 до тех пор, пока при делении не получится нечётное число d. Здесь уже рассматриваются различные комбинации показателей степени:

от d до 2^S*d , где  S – количество делений числа (n  – 1) на 2.

Кроме того, в тестах простоты применяется изменения основания степени от 2 до (n  – 2).

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

За основу при выборе эвристического алгоритма был принят тест Миллера-Рабина, поскольку этот тест используется в шифровании (шифр RSA), и где, как известно, необходима быстрота и высокая вероятность получения больших случайных простых чисел.

Алгоритм теста Миллера-Рабина [1] состоит в следующем:

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

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

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

 a^d = 1 (mod n)

и существует целое число s, 0 =< s < S, такое, что 

 a^(2^s*d) = (n – 1) (mod n)

Число a определяется на интервале целых чисел от 2 до (n – 2).

Исследования расчетов по модулю n теста Миллера-Рабина показали, что для простых чисел  n имеется хотя бы одна комбинация чисел a и s, для которой расчеты по модулю n теста Миллера-Рабина состоят из одних чисел 1 и  (n – 1). При этом, для s > 1 в этой последовательности должно быть хотя бы одно число (n – 1).  

Для составных чисел таких комбинаций чисел a и s не существует.

Поэтому имеет место предположение:

если существует комбинации чисел a  и  s  для числа n такая, что расчеты по модулю  n теста Миллера-Рабина для этой комбинации состоят из последовательности чисел из  одних чисел 1 и  (n – 1), а для s > 1 в этой последовательности есть числа (n – 1), то число n  будет простым числом.

Это необходимое и достаточное условие.

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

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

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

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

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

 P = a^(2^(S-1)*d) (mod n)

Если для всех чисел Р  расчеты по модулю n равны либо 1, либо (n – 1), и при этом, только для S > 1, существует хоть одно из чисел Р, которое равно (n – 1),

то число n будет простым числом.

 Если среди этой последовательности Р для S > 1 нет чисел, равных (n – 1), то необходим цикл по s с целью определению последовательностей чисел Р для чисел а от 2 до А по следующей формуле

P = a^(2^s*d) (mod n)  

где s меняется от (S - 2) до 0.

Цикл заканчивается в следующих случаях:

- если для всех чисел Р новой последовательности (для s = 0) расчеты по модулю n равны либо 1, либо (n – 1), то число n будет простым числом;

- если для всех чисел Р новой последовательности (для s > 0) расчеты по модулю n равны либо 1, либо (n – 1), и при этом существует хоть одно из чисел Р, которое равно (n – 1), то число n будет простым числом;

- если одно из чисел Р новой последовательности имеет расчеты по модулю n, не равные ни 1, ни (n – 1), то число n будет составным.

Были проведёны тестовые расчёты на нечётных числах от 1 до 750 000 000, которые показали надёжность алгоритма. В этих расчеты одновременно для каждого нечётного числа проводилась проверка на множители и проверка на выполнение условий эвристического алгоритма.

Число А выбирается равное 15,  с запасом – пока подтверждено только несколько чисел, которые становятся составными при a = 11.

Расчёты показали, что количество изменений числа s в среднем равно 4, при этом есть единичные результаты при s = 8.

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

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

Настоящая работа позволяет тесту Миллера–Рабина отказаться от вероятностных способов поиска псевдопростых чисел, и определять простые числа алгоритмическим методом.

Тестовые расчёты показали, что эвристический алгоритм определяет все простые числа на диапазоне нечётных чисел от 1 до 750 000 000. Данные результаты можно распространить на любой диапазон натуральных чисел. Следовательно, можно говорить о том, что получен эвристический алгоритм определения всех простых чисел среди натуральных чисел с учётом возможности компьютера.

Данный алгоритм является достаточным, имеет высокое быстродействие. В большинстве случаев на отрезке (1, 750 000 000) простое число находится через 5 раундов.

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

1. Василенко О. Н. Теоретико-числовые алгоритмы в криптографии, М.: МЦНМО, 2003, - 328 c.




Рецензии:

18.10.2019, 13:56 Мирмович Эдуард Григорьевич
Рецензия: Работа нормальная. Несмотря на искусственные "натяжки" по аспектам актуальности и новизны, после устранения замечаний рецензента она может быть опубликована. Замечания. 1. Если автору не нравятся фундаментальные работы по проблеме простых чисел и теоремам Ферма, на которые он не хочет ссылаться, то упомянуть и раскритиковать (по его мнению) массу работ по этим проблемам в настоящем журнале непременно надо. Их легко найти по поисковой системе журнала. В противном случае может сложиться впечатление, что автор впервые вообще и впервые в данном журнале представляет такую работу по простым числам. Рецензент в этом ещё заинтересован, т.к. по тем работам он давал расширенные рецензии касательно проблемs простых чисел, и в очередной статье на эту тему неплохо было бы и на рецензии среагировать. Это было бы порядочно и щепетильно. 2. Но даже на единственную работу по криптографии в работе ссылки нет, и читателю не ясно, какое отношение имеет криптография к предложенному усовершенствованию алгоритма Миллера-Рабина. В данном виде, без учёта замечаний рецензента работа к публикации не рекомендуется. Учесть данные замечания несложно и статья станет по этой теме по-настоящему интересной.

18.10.2019 16:16 Ответ на рецензию автора Усов Геннадий Григорьевич:
Уважаемый Эдуард Григорьевич! Благодарю Вас за рецензию к моей статье. Вы правильно сказали. Я впервые представляю работу по простым числам. Простые числа меня заинтересовали около года назад. Работа заключалась в поиске закономерностей в большом мире простых чисел. Существует масса работ по определению простоты чисел. В основном эти работы основаны на теореме Ферма в разной интерпретации. Однако я не нашел работ, в которых разбираются результаты этих работ: что получается, когда идут вычисления по модулю. И такие закономерности были найдены. Данные закономерности позволили уйти от вероятностных методов, при которых определяются псевдопростые числа, и прийти к алгоритмическим методам, что позволило говорить о достаточности при определении простых чисел. За основу был взят тест Миллера-Рабина, как самый распространённый тест простоты. Настоящая работа позволяет тесту Миллера –Рабина отказаться от вероятностных способов поиска псевдопростых чисел, и определять простые числа алгоритмическим методом. Поскольку я работал только с тестом Миллера-Рабина, то, по моему мнению, достаточно одной работы. Я сделал ссылку на работу. А также расширил новизну работы. Постараюсь в ближайшее время ознакомиться с расширенными рецензиями касательно проблемы простых чисел.



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

27.10.2019, 5:49 Усов Геннадий Григорьевич
Отзыв: Уважаемый Эдуард Григорьевич! Глубоко извиняюсь за задержку ответа на рецензию касательно проблемы простых чисел. Я ознакомился с расширенными рецензиями в настоящем журнале и согласен с Вами в том, что существует много работ по проблеме простых чисел. И пока будет интерес к простым числам со стороны исследователей количество работ по этим числам будет только возрастать. Мне интересны работы по проблеме простых чисел и по теоремам Ферма. Конечно, необходимо сравнение результатов настоящей работы с уже существующими тестами простоты и детерминированными алгоритмами. Однако в настоящей работе рассматривается несколько иной, новый взгляд на применение проблемы «простых чисел»: я не ищу новый тест простоты, я стараюсь видоизменить существующий тест простоты, превратить этот тест простоты из вероятностного теста в детерминированный алгоритм. Кажется, такой вариант работ с тестами простоты ещё не рассматривался. И именно по этому имеет место ссылка только на одну работу, в которой указан тест Миллера-Рабина. А поскольку порядок применения формул и условия теста Миллера-Рабина несколько поменялись, я обозначил в работе построение эвристического алгоритма с применением формул Миллера-Рабина.


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


 
 

Вверх