Есть ли серьезная неэффективность в этом псевдокоде Миллера-Рабина в CLRS?

Question

Этот вопрос может на самом деле не иметь ничего общего с процедурой проверки первичности Миллера-Рабина; это может только легкий анализ некоторого простого псевдокода.

На стр. 969 CLRS (Введение в алгоритмы 3ed) представлена ​​вспомогательная функция для Миллера-Рабина:

WITNESS(a, n)
    let t and u be such that t >= 1, u is odd, and n-1 = 2^t u
    x_0 = MODULAR-EXPONENTIATION(a, u, n)
    for i = 1 to t
        x_i = x_{i-1}^2 mod n
        if x_i == 1 and x_{i-1} != 1 and x_{i-1} != n-1
            return TRUE
    if x_t != 1
        return TRUE
    return FALSE

Я скопировал вышеизложенное именно из учебника.

Теперь, зная только, что MODULAR-EXPONENTIATION возвращает результат от 0 до n-1 включительно, я думаю, что приведенный выше псевдокод полностью эквивалентен

WITNESS(a, n)
    let t and u be such that t >= 1, u is odd, and n-1 = 2^t u
    x_0 = MODULAR-EXPONENTIATION(a, u, n)
    if x_0 == 1 or x_0 == n-1
        return FALSE
    else
        return TRUE

Если так, то, возможно, что-то не так с исходной реализацией, поскольку, если я не ошибаюсь, свидетельство Миллера-Рабина требует какого-то цикла. Может кто-нибудь привести простой контрпример, чтобы показать, что я не прав?

Answer 1

Тест простоты Миллера-Рабина разработан для ИСТИНЫ, если n - простое число, поэтому возвращаемое значение FALSE должно применяться только к составным числам. Давайте проверим это с помощью небольшой программы на Python.

def wrongwitness(a, n):             #implementation of your shortcut
    u = n - 1
    t = 0
    while u % 2 == 0:               #n - 1 = 2^t * u
        u //= 2
        t += 1

    x_0 = pow(a, u, n)              #x0 = a ^ u (mod n), oops, where is t?

    if x_0 == 1 or x_0 == n - 1:
        return False
    else:
        return True

primes = [5, 7, 11, 13, 17, 19, 23, 29, 31]

for p in primes:         
    for a in range(2, p):           #1 < a < p
        if not wrongwitness(a, p):  #witness returned FALSE, though we have a prime number
            print("Found counter example: a = ", a, "and p = ", p )

Это дает нам множество контрпримеров для вашей быстрой реализации. a = 2 а также p = 5 или же a = 3 а также p = 7, На самом деле все (p - 1, p) кортежи являются встречными примерами. Таким образом, нет ярлыка, вы должны проверить все квадратные корни a^(n-1) как объяснено в вашем учебнике.

PS: Но есть способы уменьшить количество вычислений, которые вы должны выполнить. Подмножества свидетелей были определены для n до 3 317 044 064 679 887 385 961 981. Так, для n < 1 373 653, например, достаточно просто проверить a=2 и a=3.

Answer 2

Для одного в книге мы имеем WITNESS(2, 5) == FALSE

Для краткости у нас есть WITNESS(2, 5) == TRUE следовательно, ярлык неправильный.

Кстати, следующая альтернативная реализация действительна и более эффективно завершается немедленно во всех случаях, когда она находит x_i == 1,

WITNESS(a, n)
    let t and u be such that t >= 1, u is odd, and n-1 = 2^t u
    x_0 = MODULAR-EXPONENTIATION(a, u, n)
    for i = 1 to t
        x_i = x_{i-1}^2 mod n
        if x_i == 1 
            if x_{i-1} != 1 and x_{i-1} != n-1
                return TRUE
            else
                return FALSE
    return TRUE