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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

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

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

Алгоритм:

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

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

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

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

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

В начале XIII века Леонардо Пизанский вывел последовательность чисел, одно из свойств которой в том, что n-ное число Фибоначчи F_n может быть простым только для простых n, за исключением n=4. Это свойство может быть использовано при проверке чисел Фибоначчи на простоту.

В XVII веке французский математик Марен Мерсенн занимался исследованием чисел вида 2^n-1, позднее названных в его честь числами Мерсенна. Поиск простых среди этих чисел достаточно прост благодаря тесту Люка-Лемера, позволяющему довольно быстро находить решение. Именно поэтому числа Мерсенна являются наиболее большими среди ныне известных простых чисел. В переписке Мерсенна и Ферма были высказаны еще несколько идей относительно простых чисел. Так, Ферма обнаружил, что если целое число a не делится нацело простое число p, то число a^{p-1}-1 всегда делится на p (Малая теорема Ферма). Позднее теорема была обобщена Эйлером. На малой теореме Ферма основаны несколько тестов простоты. Также Ферма предположил, что простыми являются числа вида 2^{2^{k+1}} при k \le 4. Контрпример к этому утверждению был впоследствии найден Эйлером. Для проверки чисел Ферма на простоту существует эффективный тест Пепина.

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

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

Существующие алгоритмы проверки числа на простоту могут быть разделены на две категории: истинные тесты простоты и вероятностные тесты простоты. Истинные тесты результатом вычислений всегда выдают факт простоты либо составности числа, вероятностный тест дает ответ о составности числа либо его несоставности с некоторой вероятностью \epsilon. Если сказать проще, то вероятностный алгоритм говорит, что число скорее всего не является составным, однако в итоге оно может оказаться как простым, так и составным. Числа, удовлетворяющие вероятностному тесту простоты, но являющиеся составными, называются псевдопростыми.

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

А также:

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

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

См. также[править | править вики-текст]

Литература[править | править вики-текст]