Публикация научных статей.
Вход на сайт
E-mail:
Пароль:
Запомнить
Регистрация/
Забыли пароль?

Научные направления
Поделиться:
Статья опубликована в №73 (сентябрь) 2019
Разделы: Математика
Размещена 19.09.2019. Последняя правка: 18.10.2019.
Просмотров - 1042

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

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

к.т.н.

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


12.08.2021, 9:59 Цорин Борис Иосифович
Отзыв: Очень жаль, что эта статья была опубликована. Автор просто попробовал применять тест Миллера-Рабина ровно 14 раз, то есть с вероятностью получить "ошибочно простое число" порядка 1/300.000.000, проверил при помощи этого метода 375.000.000 наименьших нечетных чисел, не нашел "ошибочно простых чисел" и сделал вывод, что изобрел новый метод, не являющийся вероятностным.


12.08.2021, 14:05 Цорин Борис Иосифович
Отзыв: Открываем Википедию: "Число 3825123056546413051 является наименьшим числом, одновременно являющимся сильным псевдопростым по 9 основаниям 2, 3, 5, 7, 11, 13, 17, 19 и 23". Проверки "до 750 миллионов" не дают ни малейших оснований предполагать, что и далее гипотеза будет верна.


23.08.2021, 16:18 Усов Геннадий Григорьевич
Отзыв: Согласен. Так сколько оснований степени обычно перебирает тест Миллера-Рабина по Вашему мнению?


24.08.2021, 6:23 Усов Геннадий Григорьевич
Отзыв: Кстати, пример 3825123056546413051 с одной стороны хороший, а с другой стороны - не очень, так как у этого числа нет основания степени (проверял небольшие), по которым тест Ферма не даст 1. Получается, что есть куча чисел, по которым тест Миллера-Рабина не действует.


25.08.2021, 12:01 Усов Геннадий Григорьевич
Отзыв: Большое спасибо за число 3825123056546413051! Постараюсь в ближайшее время подготовить статью на основании этого числа. Извиняюсь, что не по всем статьям отвечаю, поскольку вопросов много, вопросы интересные и необходимо к ответам хорошо подготовиться. Отвечаю по тем вопросам, по которым уже готов.


25.08.2021, 15:09 Цорин Борис Иосифович
Отзыв: I. Тест Миллера-Рабина перебирает сколько угодно оснований. Хоть одно. Хоть 100500. Сколько захочет тот, кто применяет тест. Чем меньше оснований взято, тем больше шанс получить неверный результат (составное число принять за простое, такие числа называются сильными псевдопростыми). Выбрать такие основания, чтобы тест Миллера-Рабина не мог дать неверный ответ, невозможно, это вероятностный тест. II. Все сильные псевдопростые числа одновременно являются псевдопростыми числами Ферма по тому же основанию. Проверьте Вашу программу.


25.08.2021, 16:51 Цорин Борис Иосифович
Отзыв: Поправка: проверять программу не надо, невнимательно читал Ваше "не очень", программа дает правильный результат. Да, тест Ферма на нем и должен давать на очень многих числах ответ 1 по той причине, которую я написал в предыдущем отзыве. Тест Ферма хуже теста Миллера-Рабина, поэтому ответ 1 тест Ферма будет давать и при некоторых других основаниях. Есть составные числа, для которых тест Ферма дает 1 при всех основаниях, взаимно простых с ним, такие числа называются числами Кармайкла. Не знаю, является ли указанное число числом Кармайкла, но наименьшее основание, по которому тест Ферма найдет, что это число составное, - это 149491, и это делитель данного числа. Наименьшее основание для теста Миллера-Рабина, соответственно, 37.


3.09.2021, 12:41 Усов Геннадий Григорьевич
Отзыв: Данная статья не учитывает числа Кармайкла. Алгоритм в статье может определить такие числа Кармайкла, у которых есть делители, меньшие числа А. Смысл работы - это попытка уйти от вероятности в тесте. Для чисел Кармайкла, у которых относительно большие делители, может подойти тест определения составных чисел, который опубликован сегодня в настоящем журнале.


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


 
 

Вверх