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

УДК 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 раундов.

Рецензии:

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