Научный журнал

Международный журнал прикладных и фундаментальных исследований

ISSN 1996-3955

ИФ РИНЦ = 0,593

• Авторы
• Резюме
• Файлы
• Ключевые слова
• Литература

Приходько А.А. 1

---

1 ФГБОУ ВО «Кубанский государственный аграрный университет им. И.Т. Трубилина»

Оптимизация алгоритмов для поиска и проверки простых чисел является актуальной задачей, решение которой необходимо для стойкости криптографических систем. В статье рассмотрены основные алгоритмы и тесты определения простых чисел. Истинные тесты простоты чисел имеют высокую степень сложности расчета, а вероятностные тесты не могут определить точно простые числа. В данной статье рассмотрен метод определения простых чисел, основанный на теореме Вильсона. Предложены решения по снижению нагрузки на вычислительную технику, выведена формула определения простого числа. В статье определена взаимосвязь малой теоремы Ферма и теоремы Вильсона. Соотношение истинного теста простоты, основанного на теореме Вильсона, и вероятностного теста Ферма обосновывает появление псевдопростых чисел Ферма и определяет необходимые условия их проверки. При определении параметров простоты числа используется китайская теорема об остатках и теорема В. Серпинского о критерии простого числа. Приведены оптимизационные решения при проверке простого числа по теореме Вильсона. Предложена оптимизация теста простоты Ферма с уменьшением выполнения необходимых операций в два раза, также представлено обоснование такой оптимизации.

Статья в формате PDF

306 KB

теорема Вильсона

малая теорема Ферма

простые числа

алгоритм расчета простого числа

метод Эратосфена

китайская теорема об остатках

1. Коломийцева С.В., Соколова К.Н. Сравнительный анализ алгоритмов проверки чисел на простоту // Информационные технологии и высокопроизводительные вычисления: материалы V Международной научно-практической конференции. 2019. С. 90–96.

2. Дмитриев Е.А. Тест Вильсона // Приоритетные направления развития образования и науки: сборник материалов II Международной научно-практической конференции. В 2-х т. 2017. С. 54.

3. Певный А.Б., Юркина М.Н. Сложность решета Эратосфена и распределение простых чисел // Вестник Сыктывкарского университета. Серия 1: Математика. Механика. Информатика. 2020. № 4 (37). С. 66–72.

4. Чопик А.А. Применение китайской теоремы об остатках // Актуальные направления научных исследований XXI века: теория и практика. 2015. Т. 3. № 8–3 (19–3). С. 446–448.

5. Мамараимов М.Т., Уштенов Е.Р. Проблемы простых чисел и теорема о критерии простого числа. Theory and practice inthe physical, mathematical andtechnical sciences. 2012. С. 16.

6. Сикорская Г.А., Галушкин Д.А., Данильчук М.В. О методах проверки числа на простоту // Университетский комплекс как региональный центр образования, науки и культуры: материалы Всероссийской научно-методической конференции (с международным участием). 2020. С. 1560.

7. Акылбаев М.И., Уштенов Е.Р. Новая теорема о критерии простого числа // Международный журнал прикладных и фундаментальных исследований. 2014. № 1–2. С. 255–257.

8. Дмитриев А.П., Рагило П.Ю., Вайтюль И.В. О распределении простых чисел // Тезисы докладов 51-й международной научно-технической конференции преподавателей и студентов. 2018. С. 124.

Рост вычислительных мощностей для обеспечения требуемого уровня стойкости криптографических систем вызвал необходимость использовать простые числа все большей разрядности. Это привело к необходимости адаптировать трудоемкость вычислительных операций криптографических алгоритмов при нахождении простых чисел [1].

Алгоритмы проверки простых чисел могут быть разделены на две группы: истинные (детерминированные) и вероятностные тесты. Истинные алгоритмы позволяют точно определить простоту числа. Вероятностные тесты позволяют выяснить простое число или нет с определенной вероятностью ошибки [2].

На сегодняшний день существует всего два основных детерминированных алгоритма проверки простого числа, это теорема Вильсона и метод Эратосфена. Метод Эратосфена предполагает простой подбор делителей, что является достаточно сложным из-за большого количества необходимых операций [3]. Проверка простого числа по теореме Вильсона также имеет высокую сложность расчета.

При определении простых чисел высоких порядков в основном используют тест Ферма, который является вероятностным. Благодаря быстрым алгоритмам, основанным на китайской теореме об остатках [4], проверку числа можно осуществить достаточно быстро, но данный тест не позволяет проверить псевдопростые числа Ферма, которые обладают некоторыми свойствами простых чисел, но не являются ими.

Целью данной работы было найти взаимосвязь теста Ферма и теоремы Вильсона, так как нет понимания, почему тест Ферма не распознает псевдопростые числа. На сегодняшний день считается, что эти две теоремы не связаны между собой и имеют совершенно разные принципы расчета. В данной статье представлены результаты исследований, которые наглядно показывают, каким образом тест Ферма соотносится с теоремой Вильсона, что имеет большое значение для дальнейшей адаптации алгоритма поиска и проверки простых чисел.

Теорема Вильсона формулируется следующим образом: Если р простое число, то имеет место сравнение (р – 1)! + 1 ≡ 0 (mod p) (1). Так же справедлива обратная теорема: Если для целого положительного р имеет место соотношение (1), то р число простое, т.е. если сумма (р – 1)! + 1 делится на р без остатка, то число р является простым числом. Проблема заключается в том, что даже при небольших числах n, число (n – 1)! + 1 очень большое число. Например, если по данному алгоритму проверить, является ли число 997 простым, то надо проверить делимость числа 996! + 1 на 997. Данное число содержит 2556 десятичных знаков, что существенно усложняет проверку [5]. Поэтому алгоритм проверки простого числа по теореме Вильсона имеет в основном теоретическое значение и не применяется на практике.

Оптимизация алгоритма по теореме Вильсона заключается в использовании китайской теоремы об остатках. При расчете факториала предположительно простого числа р на каждом этапе находится остаток от деления на р и последующее умножение производится уже этого остатка. Пример расчета числа 97 по данному алгоритму представлен в табл. 1.

Первые четыре числа не отличаются от стандартного расчета факториала. Пятое число больше числа р и равно 120, поэтому берется остаток от деления на 97, что составляет 23. Шестое число находится произведением 23 на 6 и аналогично находится остаток от деления данного числа на 97. Число с порядковым номером 96 действительно равно 96 (или р–1), что является доказательством простого числа р по теореме Вильсона. Таким образом, чтобы определить остаток от деления факториала 97, вычисление самого факториала не требуется. Более того, если последовательно перемножить числа получившегося ряда и аналогично выделять остаток от деления после каждой операции, то в результате найдем остаток от деления суперфакториала проверяемого числа.

Таблица 1

Пример расчета по алгоритму числа 97

Таблица 2

Пример расчета по алгоритму числа 57

Рассмотрим проверку составного числа по данному алгоритму. Выполним расчет по числу 57. Результаты приведены в табл. 2.

Число не прошло проверку, так как после восемнадцатого числа остаток от деления составил ноль. Соответственно, последующее число алгоритм рассчитывает как 0 × 20 = 0. Все последующие числа будут также равны нулю, поэтому условие (р – 1)! + 1 ≡ 0 (mod p) не выполняется.

Метод Эратосфена и теорема Вильсона основаны на разных принципах проверки. В первом случае происходит деление проверяемого числа на возможные множители. Теорема Вильсона основана на том принципе, что если у числа есть делители, то их произведение, умноженное на любое число, будет делить без остатка исходное число. Например, если число 35 делится на 7 и 5, то произведение 7×5×n, при любом целочисленном значении n, будет делиться без остатка на число 35. Минимальный возможный делитель для нечетного числа это 3, поэтому проверку по данному алгоритму необходимо и достаточно выполнить до числа равного р/3. По количеству необходимых операций предложенный вариант уступает методу Эратосфена, где достаточно проверить чисел [6], однако деление несопоставимых по разряду чисел требует больше времени, чем близких по количеству десятичных знаков.

На данном этапе алгоритм возможно оптимизировать, понимая особенности десятичной системы счисления. Если проверку проходит число, которое оканчивается на три, то оно может быть получено только умножением чисел вида x1 × x3 или x7 × x9. Таким образом при возведении факториала количество чисел возможно сократить.

Особенность данного метода в том, что в процессе возведения факториала есть возможность привести число р к виду p / 2n и результат расчета останется верным. При делении на другие числа алгоритм не работает корректно, что уже говорит о тесной взаимосвязи теоремы Вильсона и чисел вида 2n. В качестве примера приведен расчет числа 97, которое в процессе проверки в произвольном порядке делится на различные 2n. Результаты возведения факториала представлены в табл. 3.

Данный алгоритм основан на китайской теореме об остатках и широко применяется в программировании. Если необходимо узнать остаток от деления от произведения нескольких чисел, то на любом этапе умножения допустимо складывать и отнимать исходное число любое количество раз, и это не влияет на результат. На основании данного правила число n допустимо привести к виду n – р, если необходимо узнать остаток от деления числа р.

Рассмотрим проверку простого числа 5 по теореме Вильсона. Для этого необходимо рассчитать 4!. Расчет представляет собой вид: 1×2×3×4. Используя китайскую теорему об остатках, выражение допустимо привести к виду: 1×2×(3-5)×(4-5) = = 1×2×(-2)×(-1) = -(12)×-(22)=4.

Таблица 3

Пример проверки числа 97 с различными делителями вида 2n

При четном количестве множителей результат положительный, при нечетном – отрицательный. Если результат получается отрицательным, то необходимо брать остаток от деления отрицательного числа, то есть принцип расчета не меняется. Теорема В. Серпинского о критерии простого числа хорошо описывает данное правило [7].

Как было рассмотрено выше, доказательством того, что число простое, является наличие положительного остатка от числа Используем китайскую теорему об остатках для записи следующего равенства, на примере числа 5: 1×2 ≡ (-4)×(-3) ≡ 2 (mod 5). Запишем выражение в общем виде:

1×2×… ≡ (1 – р) × (2 – р) ×…– р ≡ n (mod p).

Если число р простое, выполняется следующее условие:

.

Преобразуем выражение в следующий вид:

.

Проверим выражение на примере числа 11:

.

Число 11 удовлетворяет условию, значит, данное простое. Эта формула хорошо известна, но имеет свои недостатки [8]. При расчете больших чисел появляется ошибка, вызванная приближенными значениями множителей.

Рассмотрим детально, как выполняется расчет:

.

Как видно, все числа из знаменателя сокращаются с числителем, умножение производится уже оставшихся значений: -3×-7×-2×-3×-2 = – 252. Дробных чисел при таком расчете получиться не может, так как знаменатель всегда будет сокращаться с числителем.

Чтобы понять закономерность, по которой формируется итоговое число, рассмотрим более высокое простое число, например 23:

Разобьем выражение на два. Рассмотрим отдельно четные и нечетные числа по знаменателю.

Далее посчитаем результат по первой части:

.

Результатом деления получилось число вида 2n. Данный результат не является случайным и имеет закономерность, при p > 8:

.

В расчете может получиться как положительное, так и отрицательное число. Принцип не меняется: если число отрицательное, то остаток от деления вычисляется от отрицательного числа. Наглядно видна связь данного выражения с малой теоремой Ферма: Если p – простое число, то оно удовлетворяет сравнению ap–1 ≡ (mod p). Как правило, проверка простых чисел ведется именно по основанию 2, так как это наименьшее число. Выведенная формула позволяет оптимизировать выражение до вида

, если число p – простое число вида 8k + 3 или 8k + 5.

, если число p – простое число вида 8k + 1 или 8k + 7.

Разделение проверяемых чисел на две группы обусловлено количеством умножений отрицательных чисел, что наглядно видно из расчета, приведенного выше.

Данное условие является необходимым, но не достаточным признаком простого числа. Для полного доказательства простого числа необходимо решить вторую часть уравнения и доказать, что

.

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

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

Библиографическая ссылка