СРАВНИТЕЛЬНЫЙ АНАЛИЗ АЛГОРИТМОВ ОПРЕДЕЛЕНИЯ ПРОСТОТЫ ЧИСЛА

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

Основные определения

Введем некоторые определения, которые будут использованы в работе. 

Определение 1. Простое число – натуральное (целое положительное) число ℕ, которое имеет ровно два различных натуральных делителя – единицу и самого себя.

Определение 2. Составное число – натуральное (целое положительное) число ℕ, которое не является простым.

Определение 3. Тест простоты – алгоритм, который по заданному натуральному числу ℕ позволяет точно или с некоторой долей вероятности определить, является ли это число простым.

Определение 4. Криптография – наука о методах обеспечения конфиденциальности, целостности данных, аутентификации, а также невозможности отказа от авторства.

Определение 5. НОД(a,b) = d, d-наибольший общий делитель, если

1)

2)

Введение

Дискретная математика — важнейшее направление современной математики. Задачи этой дисциплины являются одними из самых трудноразрешимых. Например, решение задачи факторизации, которая заключается в разложении числа на простые множители, на практике сводится к поиску простых чисел, что приводит к проблеме простоты.

Постановка проблемы

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

Тесты простоты

Следует отметить, что существующие алгоритмы проверки простоты могут быть разделены на две больших категории: истинные (детерминированные) и вероятностные тесты. Алгоритмы первой категории позволяют точно определить простоту или составность числа. А те, что относятся ко второй категории, позволяют это выяснить, но с некоторой вероятностью ошибки. Многократное их повторение для одного числа, но с разными параметрами, обычно позволяет сделать вероятность ошибки сколь угодно малой величиной.

Перебор делителей

Тип теста: детерминированный

Сложность алгоритма:

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

Алгоритм: представлен на рисунке 1 в виде блок-схемы.

Рисунок 1. Алгоритм проверки числа на простоту при помощи перебора делителей.

Практическое применение: в чистом виде не используется из-за сравнительно большой вычислительной сложности. Деление на маленькие простые числа используется как один из шагов во многих тестах.

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

Тип теста: детерминированный

Сложность алгоритма:

Описание: натуральное число n > 1— простое число тогда и только тогда, когда (mod n)

Алгоритм: представлен на рисунке 2 в виде блок-схемы.

Рисунок 2. Алгоритм проверки числа на простоту при помощи теоремы Вильсона

Практическое применение: не применяется из-за трудности вычисления

(n-1)! при больших числах n.

Тест Агравал—Кайал—Саксена (AKS)

Тип теста: детерминированный

Сложность алгоритма:

Описание: единственны полиномиальный детерминированный алгоритм проверки числа на простоту. Если существует  такое что  и для любого a от 1 до  выполняется сравнение  то n – либо простое число, либо степень простого числа.

Алгоритм: представлен на рисунке 3 в виде блок-схемы.

Рисунок 3. Алгоритм проверки числа на простоту при помощи теста AKS

Практическое применение: в качестве детерминированной полиномиальной проверки на простоту.

Критерий Поклингтона

Тип теста: детерминированный

Сложность алгоритма:, где с – положительная константа, , зависящие от выбора алгоритма факторизации.

Описание: пусть n – натуральное число и n-1 имеет простой делитель q, причем . Если найдется целое число a, для которого выполняются условия:

1.(mod n)

2. НОД(

Тогда n является простым числом.

Алгоритм: представлен на рисунке 4 в виде блок-схемы.

Рисунок 4. Алгоритм проверки числа на простоту при помощи критерия Поклингтона

Практическое применение: для получения больших простых чисел с частично известной факторизацией n – 1.

Тест Ферма.

Тип теста: вероятностный

Сложность алгоритма: O(log²n × loglog n × logloglog n)

Описание: тест простоты, основанный на малой теореме ферма, которая гласит, что если n – простое число, то для любого целого a выполняется равенство

 или   делится на  нацело.

Алгоритм: представлен на рисунке 5 в виде блок-схемы.

Рисунок 5. Алгоритм проверки числа на простоту при помощи теста Ферма.

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

Тест Миллера-Рабина

Тип теста: вероятностный

Сложность алгоритма: O(k*log²n), k–количество раундов

Описание: пусть n > 2 – натуральное число, тогда представим число n-1 в виде

n-1 = *t , где t – нечетно, а s - неотрицательно. Число a является свидетелем простоты для числа n, если выполняется одно из условий:

 или  . Количество свидетелей простоты увеличивают достоверность алгоритма.

Алгоритм: представлен на рисунке 6 в виде блок-схемы.

Рисунок 6. Алгоритм проверки числа на простоту при помощи теста Миллера-Рабина.

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

Тест Соловея — Штрассена

Тип теста: вероятностный

Сложность алгоритма: O(log³n)

Описание: данный алгоритм характеризуется числом итераций k. В каждой итерации выбирается случайное число a < n. Если НОД (a, n) > 1, то число n - составное. В противном случае нужно выяснить, справедливо ли сравнение (mod n). Если сравнение не выполняется, то число n - составное. Если оно выполняется, то a – свидетель простоты числа n. Далее следует повторить данную процедуру, используя другое случайное число a. После нахождения количества свидетелей простоты k (число итераций) можно предположить, что n является простым числом с вероятностью .

Алгоритм:

Рисунок 7. Алгоритм проверки числа на простоту при помощи теста Соловея-Штрассена.

Практическое применение: не используется из-за недостаточной степени достоверности.

Сравнение тестов простоты

Рисунок 8. Сравнение алгоритмов проверки числа на простоту

Была проведена сравнительная характеристика различных алгоритмов определения простоты числа, по результатам которой можно построить график (рисунок 8). Нетрудно заметить, что среди тестов, которые подверглись проверке на быстродействие, самым эффективным оказался тест Миллера-Рабина. Рассмотрим его программную реализацию в виде консольного приложения.

Программная реализация теста Миллера-Рабина

Рисунок 9. Демонстрация программной реализации алгоритма Миллера-Рабина.

Заключение

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

Список литературы:

1. Додонова Н.Л. Конспект лекций по дисциплине алгебраические структуры и теория чисел. Самара, 2016
2. Шнайер, Б.М. Прикладная криптография/ Б.М.Шнайер - ТРИУМФ 2002. – 816 с.