Проверка чисел на простоту — это алгоритм определения является ли число простым.
Введение
Одним из главных ветвей сегодняшней математики является направление дискретной математики. Проблемы, стоящие перед этой дисциплиной, числятся среди наиболее трудноразрешимых. Можно привести пример решения задачи факторов, согласно которой необходимо разложить число на простые сомножители. Но фактически она заключается в нахождении простых чисел, откуда возникает эта задача.
Основополагающие определения
Главными определениями являются следующие.
Простое число – это натуральное, целое положительное число n, которое делится только на единицу и на себя.
Составным числом называется натуральное, целое положительное число n, не являющееся простым.
Под тестом на простоту понимается алгоритм, согласно которому возможно точно или приблизительно выяснить, принадлежит ли данное натуральное число n к разряду простых.
Под криптографией понимается научное направление о способах, которые обеспечивают конфиденциальность, сохранность данных, а также невозможность отказаться от авторских прав.
Постановка задачи
С точки зрения науки задача, состоящая в диагнозе простое ли число, представляет интерес, поскольку на сегодня не существует единообразной формализованной формы записи простого числа. Но простые числа значительных размеров применяются в криптографических системах с открытым ключом, и проблема выявления простого числа считается нетрадиционной задачей. Не сложные способы, как, например, способ переборки, не годятся для практического применения по причине того, что для них необходимы значительные ресурсы. То есть, применение оптимального метода на простоту числа, даёт возможность увеличить быстродействие и повысить надёжность алгоритмов в криптографических системах.
Тесты простоты
Необходимо заметить, что все известные алгоритмы определения простоты чисел, можно разделить на группы:
- Дающие истинный результат (детерминированные).
- Тесты, позволяющие определить вероятность того, что число окажется простым.
Первая группа алгоритмов даёт возможность сказать простое число или составное. Вторая группа алгоритмов определяет только вероятность отнесения числа к группе простых. Но многочисленный повтор вероятностного алгоритма для одного и того же числа с различными параметрическими характеристиками, как правило, делает величину ошибки очень незначительной.
Переборка делителей
Данный алгоритм относится к первой группе и определяет простоту числа методом полного перебора любых потенциально вероятных делителей. Структура этого метода тестирования изображена на рисунке один.
Рисунок 1. Переборка делителей. Автор24 — интернет-биржа студенческих работ
На практике данный алгоритм в исходном варианте не применяется, так как требует относительно больших вычислительных мощностей. Но разделение на небольшие простые числа применяется в качестве одного из действий в некоторых тестах.
Метод Вильсона
Этот алгоритм тоже относится к первой группе. Натуральное число n больше единицы будет простым только лишь в определённых случаях. Структура алгоритма изображена на рисунке два.
Рисунок 2. Метод Вильсона. Автор24 — интернет-биржа студенческих работ
Этот алгоритм так же мало используется, так как возникают проблемы при большом числе n.
Метод Агравал—Кайал—Саксена (AKS)
Этот тест также первой группы определения простого числа, который основан на полиномах. Когда есть число r, принадлежащее множеству Z, такое что показатель числа n по модулю r, больше логарифма в квадрате n и для каждого a от 1 до корня квадратного их функции Эйлера по r умноженной на логарифм n справедливо равенство (x+a) в степени n тождественно равно x в степени n плюс a по модулю x в степени r минус единица, n, тогда n – или простое число, или является простым числом, возведённым в степень. Блок-схема этого метода изображена на рисунке три.
Рисунок 3. Метод AKS. Автор24 — интернет-биржа студенческих работ
Данный алгоритм применяется как проверка простоты числа первой группы.
Алгоритм Поклингтона
Данный алгоритм так же относится к первой группе. Уровень сложности данного способа можно определить по формуле: La в степени n [a, c]. Здесь с — положительная постоянная, переменная «a» может принимать значения от нуля до единицы включительно.
Алгоритм можно описать следующим образом. Если n является натуральным числом и n – 1 может иметь простой делитель q, где q> корень квадратный из n минус единица, и если можно найти целое число a, причём справедливы два условия:
- a в степени (n-1) по модулю n тождественно равно единице;
- наибольший общий делитель (a в степени n-1/q, -1, n) = 1,
то справедливо утверждение, что n простое число. Блок-схема этого метода изображена на рисунке четыре.
Рисунок 4. Алгоритм Поклингтона. Автор24 — интернет-биржа студенческих работ
Данный способ находит применение на практике при нахождении простых чисел значительных размеров и когда есть частичные данные о факторинге n – 1.
Алгоритм Ферма
Данный способ тестирования на простоту числа считается вероятностным и относится ко второй группе. Данный способ основывается на теореме Ферма. Она формулируется следующим образом: есть число n и если оно является простым, то для любого целого числа а должно выполняться условие: a в степени (n-1) тождественно равно единице по модулю n должно делиться на n без остатка.
Схема этого метода изображена на рисунке пять.
Рисунок 5. Алгоритм Ферма.
На практике этот алгоритм как таковой не применяется, но заложен в основу некоторых других способов, проверяющих простоту чисел.
Алгоритм Миллера-Рабина
Также относится ко второму типу алгоритмов, то есть является вероятностным. Уровень его сложности можно определить по формуле: О (к • lоg2n), где к – это число проходов. Коротко суть метода можно описать так: если n > 2 является натуральным числом, то можно выразить число n –1 как n –1 равно 2 в степени s, умноженное на t , где t является нечётным, а s должно быть положительным. Тогда числовое значение a может выступать как свидетель простоты числа n, при выполнении хотя-бы одного условия:
- a в степени t тождественно равно единице по модулю n;
- существует целое число r
Уровень достоверности алгоритма возрастает при увеличении числа свидетелей, подтверждающих простоту числа.
Блок-схема этого алгоритма изображена на рисунке шесть.
Рисунок 6. Метод проверки простоты числа посредством алгоритма Миллера-Рабина. Автор24 — интернет-биржа студенческих работ
Практическое использование этот метод находит в криптосистемах, где имеется открытый ключ. Даёт возможность выполнить проверку чисел на принадлежность к группе простых за относительно небольшой промежуток времени при достаточно высокой степени вероятности.
