[PYTHON] Verständnis und Implementierung des Tonelli-Shanks-Algorithmus (2)

Einführung

Der vorherige Artikel war hier.

Implementierung

Wiederholen wir zunächst die diesmal angenommenen Bedingungen.

Wenn $ n $ ein Vielfaches von $ p $ ist, ist $ n \ equiv 0 \ {\ rm mod} \ p $ schwer als Rest zu bezeichnen, daher werde ich es dieses Mal ausschließen (ausnahmsweise werde ich es in den Code aufnehmen).

Legendre Symbol

\left(\begin{array} nn\\\ p \end{array}\right) := n^{\frac{p-1}{2}} \equiv \begin{cases} 1 \ {\ rm mod} \ p \ Leftrightarrow n ist der quadratische Rest \\\ -1 \ {\ rm mod} \ p \ Leftrightarrow n ist ein nicht quadratischer Rest \end{cases}

war. Hier natürlich, wenn $ n $ ein Vielfaches von $ p $ ist $\left(\begin{array} nn\\\ p \end{array}\right) = 0$ Daher erfolgt hier die Ausnahmebehandlung.

Beachten Sie, dass "pow (a, b, c)" $ a ^ b \ {\ rm mod} \ c $ [^ 2] darstellt.

python


def legendre_symbol(n, p):
    ls = pow(n, (p - 1) // 2, p)
    if ls == 1:
        return 1
    #Die Pow-Funktion ist 0~ p-Gibt einen Wert im Bereich von 1 zurück
    elif ls == p - 1:
        return -1
    else:
        # ls ==0, dh wenn n ein Vielfaches von p ist
        raise Exception('n:{} = 0 mod p:{}'.format(n, p))

Wenn p eine Primzahl ist, die durch 4 geteilt wird und einen Rest von 3 hat

x = \pm n^{\frac{p+1}{4}}

War die Antwort. Wir definieren auch eine check_sqrt Funktion, die bestätigt, dass die Antwort korrekt ist.

python


#Grundsätzlich sollte hier kein Assertionsfehler auftreten
def check_sqrt(x, n, p):
    assert(pow(x, 2, p) == n % p)

def modular_sqrt(n, p):
    if p % 4 == 3:
        x = pow(n, (p + 1) // 4, p)
        check_sqrt(x, n, p)
        return [x, p - x]
    else:
        #Ich werde erklären
        pass

Wenn p eine Primzahl ist, die durch Teilen durch 4 übrig bleibt

Hier ist die Implementierung des Tonelli-Shanks-Algorithmus.

Step 1.

p-1 = Q \cdot 2^S

($ Q $ ist eine ungerade Zahl und $ S $ ist eine positive ganze Zahl).

In Python bedeuten Großbuchstaben häufig Konstanten. Verwenden Sie daher Kleinbuchstaben "q, s".

python


def modular_sqrt(n, p):
    ...
    else:
        # Step 1.
        q, s = p - 1, 0
        while q % 2 == 0:
            q //= 2
            s += 1
    ...

Step 2.

Wählen Sie nach dem Zufallsprinzip $ z $ aus, was ** quadratischer Nichtrest ** ist.

Wie ich letztes Mal erwähnt habe, ist die Hälfte ein nicht quadratischer Überschuss, also runde ich von 2 $.

Der Grund, warum wir nicht mit $ 1 $ beginnen, ist, dass $ x $, also $ x ^ 2 \ equiv 1 \ {\ rm mod} p $, für jedes $ p $ selbstverständlich existiert ($ x = 1 $). Weil $ 1 $ ein quadratischer Überschuss ist.

python


def modular_sqrt(n, p):
    ...
    else:
        # Step 1.
        q, s = p - 1, 0
        while q % 2 == 0:
            q //= 2
            s += 1
        
        # Step 2.
        z = 2
        while legendre_symbol(z, p) != -1:
            z += 1
    ...

Step 3.

\begin{cases} M_0 = S\\\ c_0 = z^Q\\\ t_0 = n^Q\\\ R_0 = n^{\frac{Q+1}{2}} \end{cases}

Dies bleibt gleich. Definieren Sie es wie zuvor in Kleinbuchstaben.

python


def modular_sqrt(n, p):
    ...
    else:
        ...
        # Step 2.
        z = 2
        while legendre_symbol(z, p) != -1:
            z += 1

        # Step 3.
        m, c, t, r = s, pow(z, q, p), pow(n, q, p), pow(n, (q + 1) // 2, p)
    ...

Step 4.

  1. Wenn $ t_i \ equiv 1 $ ist, ist $ \ pm R_i $ die Quadratwurzel von $ n $ und verlässt die Schleifenanweisung.

  2. Wenn nicht, aktualisieren Sie den Wert wie folgt:

\begin{cases} M_ {i + 1} = \ left (\ left (t_i \ right) ^ {2 ^ {j}} \ equiv 1 Minimum j, aber 0

Nun gibt es zwei ergänzende Erklärungen, um dies umzusetzen.

Der erste.

Wenn $ M_ {i + 1} $ gefunden wird, wird es in der Reihenfolge in $ j = 1, 2, \ cdots $ unterteilt, aber "$ t_i $ wird mit $ 2 $ multipliziert und $ (t_i) ^ 2 $ multipliziert Wenn nicht, multiplizieren Sie $ t_i $ mit $ 4 $, um $ (t_i) ^ 4 $ zu berechnen, und prüfen Sie, ob es 1 wird. Der folgende Code ist etwas verschwenderisch. Glaubst du nicht, dass es viele gibt? (M_update entspricht $ M_ {i + 1} $)

python


for j in range(1, m):
    if pow(t, pow(2, j), p) == 1:
        m_update = j
        break

Wenn Sie $ (t_i) ^ 2 $ berechnet haben, können Sie es quadrieren, um $ (t_i) ^ 4 $ zu erhalten. Lassen Sie es uns also wiederverwenden [^ 3].

python


pow_t = pow(t, 2, p)
for j in range(1, m):
    if pow_t == 1:
        m_update = j
        break
    pow_t = pow(pow_t, 2, p)

Der Zweite.

b_i = \left(c_i\right)^{2^{M_i - M_{i+1}-1}}

Wenn Sie definieren, kann die Wertaktualisierung wie folgt sauber geschrieben werden. Dieses Symbol finden Sie auch in Wikipedia.

\begin{cases} M_ {i + 1} = \ left (\ left (t_i \ right) ^ {2 ^ {j}} \ equiv 1 Minimum j, aber 0

Letztes Mal dachte ich, es wäre verwirrend, mehr Variablen einzuführen, also habe ich es weggelassen.

Basierend auf den beiden oben genannten Punkten können Sie den Code wie folgt schreiben.

python


def modular_sqrt(n, p):
    ...
    else:
        ...
        # Step 3.
        m, c, t, r = s, pow(z, q, p), pow(n, q, p), pow(n, (q + 1) // 2, p)
        
        # Step 4.
        while t != 1:
            pow_t = pow(t, 2, p)
            for j in range(1, m):
                if pow_t == 1:
                    m_update = j
                    break
                pow_t = pow(pow_t, 2, p)
            b = pow(c, int(pow(2, m - m_update - 1)), p)
            m, c, t, r = m_update, pow(b, 2, p), t * pow(b, 2, p) % p, r * b % p

        #Bestätigung der Antwort
        check_sqrt(r, n, p)
        return [r, p - r]

Verwenden Sie als Implementierungshinweis sowohl $ M_i $ als auch $ M_ {i + 1} $, wenn Sie auf $ c_ {i + 1}, t_ {i + 1}, R_ {i + 1} $ aktualisieren Wenn Sie also "m_update = j" gesetzt haben, aktualisieren Sie "m" nicht sofort.

Andere

Es ist tatsächlich möglich zu überprüfen, ob $ p $ eine Primzahl in der Polynomzeit ist [^ 4].

python


from gmpy2 import is_prime

is_prime(p)

Oder

python


from Crypto.Util.number import isPrime

isPrime(p)

Eine schnelle Beurteilung der Primzahl ist möglich.

Ich denke, beide sind Module, die nicht standardmäßig enthalten sind, also müssen Sie sie mit pip3 installieren.

Ganzer Quellcode

python


#!/usr/bin/env python3

from Crypto.Util.number import isPrime
# from gmpy2 import is_prime

def legendre_symbol(n, p):
    ls = pow(n, (p - 1) // 2, p)
    if ls == 1:
        return 1
    elif ls == p - 1:
        return -1
    else:
        # in case ls == 0
        raise Exception('n:{} = 0 mod p:{}'.format(n, p))

def check_sqrt(x, n, p):
    assert(pow(x, 2, p) == n % p)

def modular_sqrt(n:int, p:int) -> list:
    if type(n) != int or type(p) != int:
        raise TypeError('n and p must be integers')

    if p < 3:
        raise Exception('p must be equal to or more than 3')

    if not isPrime(p):
        raise Exception('p must be a prime number. {} is a composite number'.format(p))

    if legendre_symbol(n, p) == -1:
        raise Exception('n={} is Quadratic Nonresidue modulo p={}'.format(n, p))

    if p % 4 == 3:
        x = pow(n, (p + 1) // 4, p)
        check_sqrt(x, n, p)
        return [x, p - x]
    
    # Tonelli-Shanks
    q, s = p - 1, 0
    while q % 2 == 0:
        q //= 2
        s += 1
    z = 2
    while legendre_symbol(z, p) != -1:
        z += 1
    m, c, t, r = s, pow(z, q, p), pow(n, q, p), pow(n, (q + 1) // 2, p)
    while t != 1:
        pow_t = pow(t, 2, p)
        for j in range(1, m):
            if pow_t == 1:
                m_update = j
                break
            pow_t = pow(pow_t, 2, p)
        b = pow(c, int(pow(2, m - m_update - 1)), p)
        m, c, t, r = m_update, pow(b, 2, p), t * pow(b, 2, p) % p, r * b % p
    check_sqrt(r, n, p)
    return [r, p - r]

print(modular_sqrt(5, 41))
# => [28, 13]

[^ 1]: Wenn eine Lösung mit $ 0 <x <p $ gefunden wird, ist das Addieren (oder Subtrahieren) von $ p $ zu diesem $ x $ ebenfalls eine natürliche Lösung, also diesmal Begrenzt auf den Bereich von $ 0 <x <p $. [^ 2]: In Python können Sie "a ** b% c" schreiben, aber die Funktion "pow" funktioniert schneller. [^ 3]: Wenn beispielsweise $ 0 <j <10 $ ist, kann der erstere die pow -Funktion bis zu 18 Mal aufrufen, während der letztere sie nur 9 Mal aufrufen kann. Es geht sehr um die Bewertung des Berechnungsbetrags, aber unter diesem Gesichtspunkt wurde letztere diesmal übernommen. In der Realität gibt es jedoch fast keinen Unterschied, da der ursprüngliche Algorithmus schnell ist, unabhängig davon, welcher verwendet wird. [^ 4]: "$ p $ ist keine Primzahl (= eine zusammengesetzte Zahl)" und "Sie können das Ergebnis der Primfaktorisierung von $ p $ sehen" sind unterschiedlich. Diesmal gehe ich auf Ersteres ein. Wenn letzteres in polymorpher Zeit durchgeführt wird, wird die Sicherheitstheorie wie die sogenannte RSA-Kryptographie zerstört. (Es ist jedoch immer noch ein ungelöstes Problem, nur weil gesagt wird, dass eine Polynomzeit nicht möglich sein wird.)

Recommended Posts

Verständnis und Implementierung des Tonelli-Shanks-Algorithmus (2)
Verständnis und Implementierung des Tonelli-Shanks-Algorithmus (1)
Style GAN verstehen und implementieren
Hinter dem Graph Drawing Algorithmus und Networkx
Vollständiges Verständnis der Konzepte von Bellmanford und Dyxtra
Tensor verstehen (2): Form
Kaninchen- und Schildkrötenalgorithmus
Löse das Spiralbuch (Algorithmus und Datenstruktur) mit Python!
Über das Verständnis des 3-Punkt-Lesers [...]
Berühre den Schein und den Stummel