Реализация алгоритма Tonelli-Shanks с использованием простого модульного квадратного корня

Я выполнил алгоритм Тонелли-Шэнкса, определенный в Википедии. Я поставил его здесь для обзора и совместного использования.

реализация символа Лежандра :

def legendre_symbol(a, p):
    """
    Legendre symbol
    Define if a is a quadratic residue modulo odd prime
    http://en.wikipedia.org/wiki/Legendre_symbol
    """
    ls = pow(a, (p - 1)/2, p)
    if ls == p - 1:
        return -1
    return ls

Основной модульный квадратный корень (я просто переименовал переменную решения R в x и n к а):

def prime_mod_sqrt(a, p):
    """
    Square root modulo prime number
    Solve the equation
        x^2 = a mod p
    and return list of x solution
    http://en.wikipedia.org/wiki/Tonelli-Shanks_algorithm
    """
    a %= p

    # Simple case
    if a == 0:
        return [0]
    if p == 2:
        return [a]

    # Check solution existence on odd prime
    if legendre_symbol(a, p) != 1:
        return []

    # Simple case
    if p % 4 == 3:
        x = pow(a, (p + 1)/4, p)
        return [x, p-x]

    # Factor p-1 on the form q * 2^s (with Q odd)
    q, s = p - 1, 0
    while q % 2 == 0:
        s += 1
        q //= 2

    # Select a z which is a quadratic non resudue modulo p
    z = 1
    while legendre_symbol(z, p) != -1:
        z += 1
    c = pow(z, q, p)

    # Search for a solution
    x = pow(a, (q + 1)/2, p)
    t = pow(a, q, p)
    m = s
    while t != 1:
        # Find the lowest i such that t^(2^i) = 1
        i, e = 0, 2
        for i in xrange(1, m):
            if pow(t, e, p) == 1:
                break
            e *= 2

        # Update next value to iterate
        b = pow(c, 2**(m - i - 1), p)
        x = (x * b) % p
        t = (t * b * b) % p
        c = (b * b) % p
        m = i

    return [x, p-x]

Если у вас есть оптимизация или вы нашли какую-либо ошибку, сообщите об этом.

11 голосов | спросил Phong 2 MaramSun, 02 Mar 2014 11:53:48 +04002014-03-02T11:53:48+04:0011 2014, 11:53:48

2 ответа


6

Хорошая работа! Мне нечего прокомментировать в этом коде. Вы написали простой ясный код, единственная сложность которого связана со сложностью выполняемой операции. Было бы неплохо включить некоторые из ваших внешних комментариев (например, переименования R и n) в самом коде, чтобы кто-то мог следить за документацией по википедии. Вы можете также включить часть этой документации.

Для справки, в остальной части этого обзора предполагается, что код функционирует правильно; Сегодня вечером у меня нет моей математической головы.

Кажется, что один случай избыточного кода, если m никогда не может быть 1, что приводит к пустым диапазонам и, следовательно, не переназначает i. В противном случае вы можете пропустить присвоение i в следующем:

i, e = 0, 2
for i in xrange(1, m):
    ...

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

# Factor p-1 on the form q * 2^s (with Q odd)
q, s = p - 1, 0
while q % 2 == 0:
    s += 1
    q //= 2

Обе операции в q могут быть уменьшены. Модуль можно переписать как двоичный и q & 1, а деление как двоичный сдвиг q >>= 1. Кроме того, вы можете использовать divmod для выполнения обеих операций сразу.

Аналогично, 2**(m - i - 1) идентичен 1 << (m - i - 1) для неотрицательных показателей.

ответил Michael Urman 3 MaramMon, 03 Mar 2014 05:17:50 +04002014-03-03T05:17:50+04:0005 2014, 05:17:50
2

Чтобы повысить переносимость на python 3, используйте // вместо / везде в вашем коде. Вы уже делаете это в строках типа q //= 2, но не в строках типа x = pow(a, (p + 1)/4, p). На самом деле, включите from __future__ import division.

Кроме того, кажется, что в нескольких тестах я вычислил 2**x был значительно медленнее, чем вычисление эквивалентного 1<<x. Так что это еще одна небольшая оптимизация, которую можно сделать.

Наконец, снова для переносимости на python 3 вы можете заменить одно использование xrange с помощью range. Я не думаю, что в этом конкретном случае будет значительная потеря производительности в python 2.

ответил James K Polk 20 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowTue, 20 Sep 2016 18:54:20 +0300 2016, 18:54:20

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132