No Image

Тест на простоту числа

СОДЕРЖАНИЕ
1 просмотров
11 марта 2020

На этой странице рассмотрим задачи while22 и while23 задачника Абрамяна: определение простоты числа и задача о нахождении наибольшего общего делителя соответственно. Ниже есть форма для проверки числа на простоту, для этого нужно ввести целое положительное число в жёлтое поле и нажать "проверить".

НОД(A, B) = НОД(B, A mod B), если B ≠ 0; НОД(A, 0) = A,

где «mod» обозначает операцию взятия остатка от деления.

Решение этой задачи смотрите на странице наибольший общий делитель.

студент 3 курса, факультет информатики Самарского университета, г.Самара

студент 3 курса, факультет информатики Самарского университета, г.Самара

студент 3 курса, факультет информатики Самарского университета, г.Самара

студент 3 курса, факультет информатики Самарского университета, г.Самара

кандидат физико-математических наук, доцент кафедры прикладной математики,

Самарского университета, г.Самара

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

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

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

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

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

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

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

1)

2)

Введение

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

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

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

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

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

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

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

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

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

Читайте также:  Android studio всплывающее сообщение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.(mod n)

2. НОД(

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

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

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

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

Тест Ферма.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Читайте также:  Текст для чат бота

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

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

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

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

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

Заключение

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

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

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

Блог про алгоритмы и все что с ними связано. Основной инструмент реализации – Python.

среда, 13 апреля 2011 г.

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

Тест простоты — алгоритм, который по заданному натуральному числу определяет, простое ли это число. Различают детерминированные и вероятностные тесты.
Определение простоты заданного числа в общем случае не такая уж тривиальная задача. Только в 2002 году было доказано, что она полиномиально разрешима. Тем не менее, тестирование простоты значительно легче факторизации заданного числа.

*-Нравится статья? Кликни по рекламе! 🙂

Мы уже разобрали методы выбора всех простых чисел, до определенного, в статье Простые числа. Пришло время рассмотреть ряд алгоритмов, под общим названием – "Тесты простоты":

Обычно перебор делителей заключается в переборе всех целых (как вариант: простых) чисел от 2 до квадратного корня из факторизуемого числа n и в вычислении остатка от деления n на каждое из этих чисел. Если остаток от деления на некоторое число m равен нулю, то m является делителем n. В этом случае либо n объявляется составным, и алгоритм заканчивает работу (если тестируется простота n), либо n сокращается на m и процедура повторяется (если осуществляется факторизация n). По достижении квадратного корня из n и невозможности сократить n ни на одно из меньших чисел, n объявляется простым.
Примечание: если у n есть некоторый делитель p, то n/p так же будет делителем, причем одно из этих чисел не превосходит .

Реализация на Python:

2.) Теорема Вильсона
Теорема теории чисел, которая утверждает, что

p — простое число тогда и только тогда, когда (p − 1)! + 1 делится на p

Практическое использование теоремы Вильсона для определения простоты числа нецелесообразно из-за сложности вычисления факториала. Таким образом, время выполнения данного алгоритма = поиску факториала. Алгоритм поиска факториала мы уже рассматривали.
Реализация:

Читайте также:  Usb vid 1a40 pid 0101

3.) Тест простоты Ферма

Простое число удовлетворяет тесту Ферма. Составной объект может пройти тест Ферма с вероятностью . Сложность разрядной операции испытания Ферма равна сложности алгоритма, который вычисляет возведение в степень.Поскольку вычисление (mod N) довольно быстрая операция, у нас возникает быстрый тест, проверяющий, является ли данное число составным. Его называют тестом Ферма по основанию а. Заметим, что тест Ферма может лишь убедить нас в том, что число N имеет делители, но не в состоянии доказать его простоту. Действительно, рассмотрим составное число N = 11 · 13 = 341, а основание в тесте Ферма выберем равным 2. Тогда = 1 mod 341, в то время как число 341 не простое. В этом случае говорят, что N — псевдопростое число (в смысле Ферма) по основанию 2. Существует бесконечно много псевдопростых чисел по фиксированному основанию, хотя они встречаются реже, чем простые. Можно показать, что для составного N вероятность неравенства
≠ 1 (mod N).
больше 1/2. Подводя итог сказанному, выпишем алгоритм теста Ферма.
Если на выходе этого алгоритма напечатано «составное, а», то мы с определенностью можем заявить, что число n не является простым, и что а свидетельствует об этом факте, т. е. чтобы убедиться в истинности высказывания, нам достаточно провести тест Ферма по основанию а. Такое а называют свидетелем того, что n составное.
Если же в результате работы теста мы получим сообщение: «правдоподобно простое», то можно заключить: n — составное с вероятностью ≤ существуют составные числа, относительно которых тест Ферма выдаст ответ правдоподобно простое, для всех взаимно простых с n оснований а. Такие числа называются числами Кармайкла. К сожалению, их бесконечно много. Первые из них — это 561, 1105 и 1729. Числа Кармайкла обладают следующими свойствами:

  • они нечетны,
  • имеют по крайней мере три простых делителя,
  • свободны от квадратов1,
  • если р делит число Кармайкла N, то р — 1 делит N — 1.

Чтобы получить представление об их распределении, посмотрим на числа, не превосходящие . Среди них окажется примерно 2, 7 • простых чисел, но только 246 683 ≈ 2,4 • чисел Кармайкла. Следовательно, они встречаются не очень часто, но и не настолько редко, чтобы их можно было игнорировать.

4.)Тест Миллера — Рабина

Вероятностный полиномиальный тест простоты. Тест Миллера — Рабина позволяет эффективно определять, является ли данное число составным. Однако, с его помощью нельзя строго доказать простоту числа. Тем не менее тест Миллера — Рабина часто используется в криптографии для получения больших случайных простых чисел.
Алгоритм был разработан Гари Миллером в 1976 году и модифицирован Майклом Рабином в 1980 году.

Комментировать
1 просмотров
Комментариев нет, будьте первым кто его оставит

Это интересно
No Image Компьютеры
0 комментариев
No Image Компьютеры
0 комментариев
No Image Компьютеры
0 комментариев
Adblock detector