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

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


Тест простоты — алгоритм, который по заданному натуральному числу определяет, простое ли это число. Различают детерминированные и вероятностные тесты.
Определение простоты заданного числа в общем случае не такая уж тривиальная задача. Только в 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 — простое число, то an-1 1 mod n.
Обратите внимание, что если n — простое число, то сравнение справедливо. Это не означает, что если сравнение справедливо, то n — простое число. Целое число может быть простым числом или составным объектом. Мы можем определить следующие положения как тест Ферма:
Если n — простое число, то an-1  1 mod n
Если n — составной объект, то возможно, что an-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 порядка величины log2(m), где m — проверяемое число.
Для данного m находятся такие целое число s и целое нечётное число t, что m − 1 = 2st. Выбирается случайное число 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 # Простое
Ещё реализации:
  1. http://en.literateprograms.org/Miller-Rabin_primality_test_%28Python%29
  2. http://code.activestate.com/recipes/410681-rabin-miller-probabilistic-prime-test/
  3. http://code.activestate.com/recipes/511459-miller-rabin-primality-test/
UPD:На сладкое, нашел на Хабре статейку, где предлагали следующее регулярное выражение для определения простоты числа:
/^1?$|^(11+?)\1+$/
Применять его следует не к самому целому числу. Вместо этого, нужно создать строку из единиц, где количество единиц соответствует самому числу и уже к этой строке применить регулярное выражение. Если совпадения нет — число простое. Так как же оно работает? Подвыражение (11+?) совпадает со строками вроде 11, 111, и т.д… Часть "\1+" будет искать далее по строке совпадения с результатами поиска первого подвыражения. В первый раз совпадение произойдет по строке «11» и потом поиск строки «11» будет произведен снова, а затем снова до конца строки. Если поиск завершится успешно, число не является простым. Почему? Потому, что будет доказано, что длина строки делится на 2 и, соответственно, само число тоже делится на два. Если совпадения не произойдет, движок регулярных выражений начнет искать строку «111» и ее повторения. Если первое подвыражение становится достаточно длинным (n/2) и совпадений по-прежнему не будет обнаружено, число будет являться простым.
Реализовывать я его не стал, не люблю регулярки(если кто напишет, жду в комменты, добавлю).

Используемая литература:
  1. http://younglinux.info/algorithm/divider
  2. Тест простоты
  3. http://masteroid.ru/content/view/1292/49/
  4. http://www.intuit.ru/department/security/mathcryptet/
  5. http://www.re.mipt.ru/infsec/2005/essay/2005_Primality_tests_survey__Kuchin.htm
  6. http://algolist.manual.ru/maths/teornum/rabmil.php