Loading [MathJax]/jax/output/HTML-CSS/jax.js

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

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

Введение


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

  1. Ввод: натуральное число N
  2. Решение (поиск случайного простого числа P)
    1. P Функция генерации произвольного натурального числа на отрезке [N,2N]
    2. Если P составное, то
      1. PP+1
      2. Если P=2N то
        1. PN
    3. Возврат «P — случайное простое»

 Время решения задачи этим алгоритмом не определено, но есть большаявероятность, что оно всегда является полиномиальным, пока имеетсядостаточно простых чисел, и они распределены более-менее равномерно. Дляпростых случайных чисел эти условия выполняются.
 Известно (теорема Евклида), что множество простых чисел бесконечно.Теорема Дирихле (1837) гласит, что если НОД(a,n)=1, то существуетбесконечно много простых чисел, сравнимых с a по модулю n. Другимисловами, простые числа распределены равномерно в классах вычетов поmodn в соответствии с функцией Эйлера φ(n) при любом значенииn. Однако, если простые числа распределены равномерно, но ихсуществует очень небольшое количество, поиск может оказаться невозможнымна практике. Чтобы решить эту вторую проблему, воспользуемся теоремой ораспределении простых чисел (1896), согласно которой количество простыхчисел в интервале [2,n] растет с увеличением n как n/log(n). Эточисло стремится к бесконечности довольно быстро, из чего можно сделатьзаключение, что даже при больших значениях n существует достаточновысокая вероятность (1/ln(n)) нахождения простого числа наугад. Изэтого можно заключить, что описанный выше алгоритм может дать ответ заполиномиальное время, если существует полиномиальный алгоритм,позволяющий убедиться в простоте сколь угодно большого числа n, чтоприводит к проблеме простоты.
 При тестировании простых чисел можно воспользоваться данным алгоритмом
 IF X - простое число, then
 \textlessmath\textgreater\{sum\^\{x-2\}\_\{1\}\{n*2\^\{x-2-n\}\}modx\{equiv1\textless/math\textgreater

Историческиесведения


 Самые первые упоминания о простых числах известны у Евклида (3 в.до н. э.). При этом первый алгоритм нахождения простых чисел былизобретен Эратосфеном (2 в. до н. э.) и известен сейчас под названиемрешето Эратосфена. Его суть в последовательном исключении из спискацелых чисел от 1 до n чисел, кратных 2,3,5 и другим уженайденным «решетом» простым числам. Значительно позже арабский математикибн ал-Банна предложил делать перебор целых чисел, не до n, а доn, что позволило уменьшить количество операций. Недостатокэтого метода заключается в том, что вместо проверки заданного числа nна простоту он предлагает последовательный перебор всех целых чисел доn, и поэтому является малоэффективным и требует значительныхвычислительных мощностей.
 В начале XIII века Леонардо Пизанский, известный как Фибоначчи,предложил последовательность чисел (названную его именем), одно изсвойств которой состоит в том, что n-ное число Фибоначчи Fn можетбыть простым только для простых n, за исключением n=4. Это свойствоможет быть использовано при проверке чисел Фибоначчи на простоту. Такжеон независимо от ибн ал-Банна предложил метод проверки чисел на простотуперебором. Этот алгоритм является истинным (или невероятностным),поскольку ответ получается всегда, однако чрезвычайно неэффективным.
 Первым, кто использовал отношения между числами для определенияпростоты, был Пьетро Антонио Катальди в своей работе о совершенныхчислах. Совершенными числами называются те, которые равны сумме своихсобственных делителей. Первые семь совершенных чисел: 6, 28, 496, 8128,33550336, 8589869056 и 137438691328. Катальди установил, что если числоn — простое и число 2n1 — также простое, то число2n1(2n1) — совершенное.
 В XVII веке французский математик Марен Мерсенн занимался исследованиемчисел вида 2n1, позднее названных в его честь числами Мерсенна.Мерсенн обнаружил, что из первых 257 чисел Мерсенна только 11 являютсяпростыми (при n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 и 257). При этом,им было сделано несколько ошибок (2n1 не является простым при р = 67или 257, и является при р = 61, 89 и 107). Поиск простых среди чиселМерсенна достаточно прост благодаря тесту Люка-Лемера, позволяющемуотносительно быстро находить решение. Именно поэтому числа Мерсеннаявляются самыми большими среди ныне известных простых чисел. В перепискеМерсенна и Ферма были высказаны ещё несколько идей относительно простыхчисел.
 Так, Ферма обнаружил, что если целое число a не делится нацело напростое число p, то число ap11 всегда делится на p (Малаятеорема Ферма). Позднее теорема была обобщена Эйлером. На малой теоремеФерма основаны несколько тестов простоты. Также Ферма предположил, чтопростыми являются числа вида 22k+1 при всех натуральных k. Этодействительно так при k=0,1,2,3,4. Контрпример к этому утверждениюбыл найден Эйлером— 225+1=4294967297=6416700417. Дляпроверки чисел Ферма на простоту существует эффективный тест Пепина. Насегодняшний день ни одного нового простого числа Ферма не было найдено.
 В числе других ученых вопросами простоты чисел занимались Эйлер,Лежандр, Гаусс. Значительные результаты в решении проблемы простоты былиполучены французским математиком Эдуардом Люка в его работах о числахФерма и Мерсенна . Именно данный им критерий простоты чисел Мерсеннаныне известен как тест Люка-Лемера.

Истинные тестыпростоты


 Существующие алгоритмы проверки числа на простоту могут быть разделенына две категории: истинные тесты простоты и вероятностные тестыпростоты. Истинные тесты результатом вычислений всегда выдают фактпростоты либо составности числа, вероятностный тест дает ответ осоставности числа либо его несоставности с некоторой вероятностьюϵ. Если сказать проще, то вероятностный алгоритм говорит, чточисло скорее всего не является составным, однако в итоге оно можетоказаться как простым, так и составным. Числа, удовлетворяющиевероятностному тесту простоты, но являющиеся составными, называютсяпсевдопростыми. Одним из примеров таких чисел являются числа Кармайкла.Также можно назвать числа Эйлера-Якоби для теста Соловея-Штрассена ипсевдопростые числа Люка.
 Одним из примеров истинных тестов простоты является тест Люка-Лемера длячисел Мерсенна. Очевидный недостаток этого теста заключается в егоприменимости только к ряду чисел определённого вида. Среди другихпримеров можно привести основанные на малой теореме Ферма

  • Тест Пепина для чисел Ферма
  • Теорема Прота для чисел Прота
  • Тест Агравала — Каяла — Саксены, первый полиномиальный тест простоты.
  • Тест Люка — Лемера — Ризеля

 А также:

  • метод перебора делителей
  • Теорема Вильсона
  • Критерий Поклингтона
  • Тест Миллера
  • Тест Адлемана — Померанса — Румели, усовершенствованный и Ленстрой
  • Тест простоты с использованием эллиптических кривых.

Вероятностные тестыпростоты


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

  • Тест Ферма
  • Тест Миллера — Рабина
  • Тест Соловея — Штрассена
  • Тест Бейли — Померанца — Селфриджа — Уогстаффа
  • .

Тесты простоты вкриптографии


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