Python алгоритмы: Тест простоты

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

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

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

1.) Перебор делителей:

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

Описание алгоритма:

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

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

def divider(n):
    i = 2
    j = 0 # флаг
    while i**2 <= n and j != 1:
        if n%i == 0:
            j = 1
        i += 1
    if j == 1:
        print ("Это составное число")
    else:
        print ("Это простое число")

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

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

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

def prime(n):
    if (math.factorial(n-1)+1) % n!=0:
        print ("Это составное число")
    else:
        print ("Это простое число")

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

Первый вероятностный метод, который мы обсуждаем, — испытание простоты чисел тестом Ферма.

Если n — простое число, то a^n-1

1 mod n.

Обратите внимание, что если n — простое число, то сравнение справедливо. Это не означает, что если сравнение справедливо, то n — простое число. Целое число может быть простым числом или составным объектом. Мы можем определить следующие положения как тест Ферма:

Если n — простое число, то a^n-1  1 mod n
Если n — составной объект, то возможно, что a^n-1  1 mod n

Простое число удовлетворяет тесту Ферма. Составной объект может пройти тест Ферма с вероятностью $\varepsilon$ . Сложность разрядной операции испытания Ферма равна сложности алгоритма, который вычисляет возведение в степень.Поскольку вычисление

(mod N) довольно быстрая операция, у нас возникает быстрый тест, проверяющий, является ли данное число составным. Его называют тестом Ферма по основанию а. Заметим, что тест Ферма может лишь убедить нас в том, что число N имеет делители, но не в состоянии доказать его простоту. Действительно, рассмотрим составное число N = 11 · 13 = 341, а основание в тесте Ферма выберем равным 2. Тогда

= 1 mod 341, в то время как число 341 не простое. В этом случае говорят, что N — псевдопростое число (в смысле Ферма) по основанию 2. Существует бесконечно много псевдопростых чисел по фиксированному основанию, хотя они встречаются реже, чем простые. Можно показать, что для составного N вероятность неравенства

≠ 1 (mod N).
больше 1/2. Подводя итог сказанному, выпишем алгоритм теста Ферма.

def primFerma(a,n):
    if a**(n-1)%n==1:
        print "правдоподобно простое"
    else:
        print "составное"

Если на выходе этого алгоритма напечатано «составное, а», то мы с определенностью можем заявить, что число n не является простым, и что а свидетельствует об этом факте, т. е. чтобы убедиться в истинности высказывания, нам достаточно провести тест Ферма по основанию а. Такое а называют свидетелем того, что n составное.
Если же в результате работы теста мы получим сообщение: «правдоподобно простое», то можно заключить: n — составное с вероятностью ≤

существуют составные числа, относительно которых тест Ферма выдаст ответ правдоподобно простое, для всех взаимно простых с n оснований а. Такие числа называются числами Кармайкла. К сожалению, их бесконечно много. Первые из них — это 561, 1105 и 1729. Числа Кармайкла обладают следующими свойствами:

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

Чтобы получить представление об их распределении, посмотрим на числа, не превосходящие

. Среди них окажется примерно 2, 7 •

простых чисел, но только 246 683 ≈ 2,4 •

чисел Кармайкла. Следовательно, они встречаются не очень часто, но и не настолько редко, чтобы их можно было игнорировать.

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

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

Пусть $~m$ — нечётное число большее 1. Число $~m-1$ однозначно представляется в виде $m-1 = 2^s \cdot t$ , где $~t$ нечётно. Целое число $~a$ , $~1 < a < m$ , называется свидетелем простоты числа $~m$ , если выполняется одно из условий:

$~a^t\equiv 1\pmod m$

или

существует целое число $~k$ , $~0\leq k<s$ , такое, что $~ a^{2^kt}\equiv -1\pmod m.$

Теорема Рабина утверждает, что составное нечётное число

m

имеет не более $\varphi(m)/4$ различных свидетелей простоты, где $\varphi(m)$ — функция Эйлера.
Алгоритм Миллера — Рабина параметризуется количеством раундов r. Рекомендуется брать r порядка величины

log 2 (m)

, где m — проверяемое число.
Для данного m находятся такие целое число s и целое нечётное число t, что

m - 1 = 2 s t

. Выбирается случайное число a, 1 < a < m. Если a не является свидетелем простоты числа m, то выдается ответ «m составное», и алгоритм завершается. Иначе, выбирается новое случайное число a и процедура проверки повторяется. После нахождения r свидетелей простоты, выдается ответ «m, вероятно, простое», и алгоритм завершается. Как и для теста Ферма, все числа n > 1, которые не проходят этот тест – составные, а числа, которые проходят, могут быть простыми. И, что важно, для этого теста нет аналогов чисел Кармайкла.
В 1980 году было доказано, что вероятность ошибки теста Рабина-Миллера не превышает 1/4. Таким образом, применяя тест Рабина-Миллера t раз для разных оснований, мы получаем вероятность ошибки 2-2t.

def toBinary(n):
    r = []
    while (n > 0):
        r.append(n % 2)
        n = n / 2
        return r

def MillerRabin(n, s = 50):  
    for j in xrange(1, s + 1):
            a = random.randint(1, n - 1)
            b = toBinary(n - 1)
            d = 1
            for i in xrange(len(b) - 1, -1, -1):
                x = d
                d = (d * d) % n
                if d == 1 and x != 1 and x != n - 1:
                    return True # Составное
                if b[i] == 1:
                    d = (d * a) % n
                    if d != 1:
                        return True # Составное
                    return False # Простое

Ещё реализации:

UPD:На сладкое, нашел на Хабре статейку, где предлагали следующее регулярное выражение для определения простоты числа:
/^1?$|^(11+?)\1+$/
Применять его следует не к самому целому числу. Вместо этого, нужно создать строку из единиц, где количество единиц соответствует самому числу и уже к этой строке применить регулярное выражение. Если совпадения нет — число простое. Так как же оно работает? Подвыражение (11+?) совпадает со строками вроде 11, 111, и т.д… Часть "\1+" будет искать далее по строке совпадения с результатами поиска первого подвыражения. В первый раз совпадение произойдет по строке «11» и потом поиск строки «11» будет произведен снова, а затем снова до конца строки. Если поиск завершится успешно, число не является простым. Почему? Потому, что будет доказано, что длина строки делится на 2 и, соответственно, само число тоже делится на два. Если совпадения не произойдет, движок регулярных выражений начнет искать строку «111» и ее повторения. Если первое подвыражение становится достаточно длинным (n/2) и совпадений по-прежнему не будет обнаружено, число будет являться простым.
Реализовывать я его не стал, не люблю регулярки(если кто напишет, жду в комменты, добавлю).

Используемая литература:

Python алгоритмы

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

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

Комментариев нет:

Отправить комментарий

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

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

Комментариев нет:

Отправить комментарий

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