Меню Закрыть

Как проверить число на простоту

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1)

2)

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Читайте также:  Abs что это в информатике

Описание: пусть 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 с.

Вопрос определения того, является ли натуральное число N <displaystyle N> простым, известен как проблема простоты.

Тестом простоты (или проверкой простоты) называется алгоритм, который, приняв на входе число N <displaystyle N> , позволяет либо не подтвердить предположение о составности числа, либо точно утверждать его простоту. Во втором случае он называется истинным тестом простоты. Таким образом, тест простоты представляет собой только гипотезу о том, что если алгоритм не подтвердил предположение о составности числа N <displaystyle N> , то это число может являться простым с определённой вероятностью. Это определение подразумевает меньшую уверенность в соответствии результата проверки истинному положению вещей, нежели истинное испытание на простоту, которое дает математически подтвержденный результат.

Содержание

Введение [ править | править код ]

Проблемы дискретной математики являются одними из самых математически сложных. Одна из них — задача факторизации, заключающаяся в поиске разложения числа на простые множители. Для её решения необходимо найти простые числа, что приводит к проблеме простоты. Задача теста простоты относится к классу сложности P, то есть время работы алгоритмов её решения зависит от размера входных данных полиномиально, что было доказано в 2002 году. Существует аналогичное, однако недоказанное, утверждение для задачи факторизации.

Читайте также:  Закрытый канал на телевизоре

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

  1. Ввод: натуральное число N <displaystyle N>
  2. Решение (поиск случайного простого числа P)
  1. P ← <displaystyle Pgets >Функция генерации произвольного натурального числа на отрезке [ N , 2 N ] <displaystyle [N,2N]>
  2. Если P <displaystyle P>составное, то
  1. P ← P + 1 <displaystyle Pleftarrow ,P+1>
  2. Если P = 2 N <displaystyle P=2N>то
  1. P ← N <displaystyle Pleftarrow ,N>
  • Возврат « P <displaystyle P>— случайное простое»
  • Время решения задачи этим алгоритмом не определено, но есть большая вероятность, что оно всегда является полиномиальным, пока имеется достаточно простых чисел, и они распределены более-менее равномерно. Для простых случайных чисел эти условия выполняются.

    Известно (теорема Евклида), что множество простых чисел бесконечно. Теорема Дирихле (1837) гласит, что если НОД ( a , n ) = 1 <displaystyle (a,n)=1> , то существует бесконечно много простых чисел, сравнимых с a <displaystyle a> по модулю n <displaystyle n> . Другими словами, простые числа распределены равномерно в классах вычетов по m o d n <displaystyle modn> в соответствии с функцией Эйлера [1] φ ( n ) <displaystyle varphi (n)> при любом значении n <displaystyle n> . Однако, если простые числа распределены равномерно, но их существует очень небольшое количество, поиск может оказаться невозможным на практике. Чтобы решить эту вторую проблему, воспользуемся теоремой о распределении простых чисел (1896), согласно которой количество простых чисел в интервале [ 2 , n ] <displaystyle [2,n]> растет с увеличением n <displaystyle n> как n / l o g ( n ) <displaystyle n/log(n)> . Это число стремится к бесконечности довольно быстро, из чего можно сделать заключение, что даже при больших значениях n <displaystyle n> существует достаточно высокая вероятность ( 1 / l n ( n ) <displaystyle 1/ln(n)> ) нахождения простого числа наугад. Из этого можно заключить, что описанный выше алгоритм может дать ответ за полиномиальное время, если существует полиномиальный алгоритм, позволяющий убедиться в простоте сколь угодно большого числа n <displaystyle n> , что приводит к проблеме простоты.

    Исторические сведения [ править | править код ]

    Самые первые упоминания о простых числах известны у Евклида (3 в. до н. э.). При этом первый алгоритм нахождения простых чисел был изобретен Эратосфеном (2 в. до н. э.) и известен сейчас под названием решето Эратосфена. Его суть в последовательном исключении из списка целых чисел от 1 <displaystyle 1> до n <displaystyle n> чисел, кратных 2 , 3 , 5 <displaystyle 2,3,5> и другим уже найденным «решетом» простым числам [2] . Значительно позже арабский математик ибн ал-Банна предложил делать перебор целых чисел, не до n <displaystyle n> , а до n <displaystyle <sqrt >> , что позволило уменьшить количество операций. Недостаток этого метода заключается в том, что вместо проверки заданного числа n <displaystyle n> на простоту он предлагает последовательный перебор [3] всех целых чисел до n <displaystyle <sqrt >> , и поэтому является малоэффективным и требует значительных вычислительных мощностей.

    В начале XIII века Леонардо Пизанский, известный как Фибоначчи, предложил последовательность чисел (названную его именем), одно из свойств которой состоит в том, что n <displaystyle n> -ное число Фибоначчи F n <displaystyle F_> может быть простым только для простых n <displaystyle n> , за исключением n = 4 <displaystyle n=4> . Это свойство может быть использовано при проверке чисел Фибоначчи на простоту. Также он независимо от ибн ал-Банна предложил метод проверки чисел на простоту перебором. Этот алгоритм является истинным (или невероятностным), поскольку ответ получается всегда, однако чрезвычайно неэффективным.

    Первым, кто использовал отношения между числами для определения простоты, был Пьетро Антонио Катальди в своей работе о совершенных числах. Совершенными числами называются те, которые равны сумме своих собственных делителей. Первые семь совершенных чисел: 6, 28, 496, 8128, 33550336, 8589869056 и 137438691328. Катальди установил, что если число n <displaystyle n> — простое и число 2 n − 1 <displaystyle 2^-1> — также простое, то число 2 n − 1 ( 2 n − 1 ) <displaystyle 2^(2^-1)> — совершенное.

    В XVII веке французский математик Марен Мерсенн занимался исследованием чисел вида [4] 2 n − 1 <displaystyle 2^-1> , позднее названных в его честь числами Мерсенна. Мерсенн обнаружил, что из первых 257 чисел Мерсенна только 11 являются простыми (при n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 и 257). При этом, им было сделано несколько ошибок ( 2 n − 1 <displaystyle 2^-1> не является простым при р = 67 или 257, и является при р = 61, 89 и 107). Поиск простых среди чисел Мерсенна достаточно прост благодаря тесту Люка-Лемера, позволяющему относительно быстро находить решение. Именно поэтому числа Мерсенна являются самыми большими среди ныне известных простых чисел. В переписке Мерсенна и Ферма были высказаны ещё несколько идей относительно простых чисел [4] .

    Читайте также:  Как наложить прозрачный фон на картинку

    Так, Ферма обнаружил, что если целое число a <displaystyle a> не делится нацело на простое число p <displaystyle p> , то число a p − 1 − 1 <displaystyle a^-1> всегда делится на p <displaystyle p> (Малая теорема Ферма). Позднее теорема была обобщена Эйлером. На малой теореме Ферма основаны несколько тестов простоты. Также Ферма предположил, что простыми являются числа вида 2 2 k + 1 <displaystyle 2^<2^>+1> при всех натуральных k <displaystyle k> . Это действительно так при k = 0 , 1 , 2 , 3 , 4 <displaystyle k=0,1,2,3,4> . Контрпример к этому утверждению был найден Эйлером— 2 2 5 + 1 = 4294967297 = 641 ⋅ 6700417 <displaystyle 2^<2^<5>>+1=4294967297=641cdot 6700417> . Для проверки чисел Ферма на простоту существует эффективный тест Пепина. На сегодняшний день ни одного нового простого числа Ферма не было найдено.

    В числе других ученых вопросами простоты чисел занимались Эйлер, Лежандр, Гаусс. Значительные результаты в решении проблемы простоты были получены французским математиком Эдуардом Люка в его работах о числах Ферма и Мерсенна . Именно данный им критерий простоты чисел Мерсенна ныне известен как тест Люка-Лемера.

    В 2002 г. был разработан детерминированный полиномиальный тест простоты, тест Агравала — Каяла — Саксены. Его появление предсказывалось существованием полиномиальных сертификатов простоты и, как следствие, тем, что задача проверки числа на простоту принадлежала классам NP и co-NP одновременно.

    Истинные тесты простоты [ править | править код ]

    Существующие алгоритмы проверки числа на простоту могут быть разделены на две категории: истинные тесты простоты и вероятностные тесты простоты. Истинные тесты результатом вычислений всегда выдают факт простоты либо составности числа, вероятностный тест дает ответ о составности числа либо его несоставности с некоторой вероятностью [2] [4] ϵ <displaystyle epsilon > . Если сказать проще, то вероятностный алгоритм говорит, что число скорее всего не является составным, однако в итоге оно может оказаться как простым, так и составным. Числа, удовлетворяющие вероятностному тесту простоты, но являющиеся составными, называются псевдопростыми [1] . Одним из примеров таких чисел являются числа Кармайкла [3] . Также можно назвать числа Эйлера-Якоби для теста Соловея-Штрассена и псевдопростые числа Люка.

    Одним из примеров истинных тестов простоты является тест Люка-Лемера для чисел Мерсенна. Очевидный недостаток этого теста заключается в его применимости только к ряду чисел определённого вида. Среди других примеров можно привести основанные на малой теореме Ферма

    Вероятностные тесты простоты [ править | править код ]

    К этой категории относятся:

    Тесты простоты в криптографии [ править | править код ]

    В настоящее время простые числа широко применяются в области защиты информации. Прежде всего, это вызвано изобретением метода шифрования с открытым ключом, который используется при шифровании информации и в алгоритмах электронной цифровой подписи. На данный момент по стандартам размер простых чисел, используемых при формировании цифровой подписи с использованием эллиптических кривых, составляет в соответствии с ГОСТ Р 34.10-2012 не менее 254 бит. Для столь больших чисел вопрос определения простоты числа является крайне сложным. Простые методы, такие, как метод перебора, непригодны для использования из-за того, что требуют чрезвычайно много вычислительных ресурсов и большого времени работы [6] .

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

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

    Рекомендуем к прочтению

    Добавить комментарий

    Ваш адрес email не будет опубликован.