introduction

L'article précédent était ici.

la mise en oeuvre

Tout d'abord, répétons les conditions supposées cette fois.

Input:
$ p $: nombre premier impair
$ n $: Entier, où $ n $ n'est pas un multiple de $ p $
Output:
$ x $: $ x ^ 2 \ equiv n \ {\ rm mod} \ p $, et $ 0 <x <n $ [^ 1]

Si $ n $ est un multiple de $ p $, $ n \ equiv 0 \ {\ rm mod} \ p $ est difficile de dire un reste, donc je vais l'exclure cette fois (à titre d'exception, je l'inclurai dans le code).

Symbole de Legendre

\left(\begin{array} nn\\\ p \end{array}\right) := n^{\frac{p-1}{2}} \equiv \begin{cases} 1 \ {\ rm mod} \ p \ Leftrightarrow n est le reste du carré \\\ -1 \ {\ rm mod} \ p \ Leftrightarrow n est un reste non carré \end{cases}

était. Ici, bien sûr, si $ n $ est un multiple de $ p $ $\left(\begin{array} nn\\\ p \end{array}\right) = 0$ Par conséquent, la gestion des exceptions est effectuée ici.

Notez que pow (a, b, c) représente $ a ^ b \ {\ rm mod} \ c $ [^ 2].

`python`


def legendre_symbol(n, p):
    ls = pow(n, (p - 1) // 2, p)
    if ls == 1:
        return 1
    #La fonction pow est 0~ p-Renvoie une valeur comprise entre 1
    elif ls == p - 1:
        return -1
    else:
        # ls ==0, c'est-à-dire lorsque n est un multiple de p
        raise Exception('n:{} = 0 mod p:{}'.format(n, p))

Quand p est un nombre premier qui est divisé par 4 et a un reste de 3

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

C'était la réponse. Nous définissons également une fonction check_sqrt qui confirme que la réponse est correcte.

`python`


#Fondamentalement, il ne devrait y avoir aucune erreur d'assertion ici
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:
        #Je vais expliquer
        pass

Lorsque p est un nombre premier qu'il reste en divisant par 4

Voici l'implémentation de l'algorithme Tonelli-Shanks.

Step 1.

p-1 = Q \cdot 2^S

($ Q $ est un nombre impair et $ S $ est un entier positif).

En Python, les lettres majuscules signifient souvent des constantes, utilisez donc la lettre minuscule 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.

Sélectionnez au hasard $ z $, qui est ** carré non-reste **.

Comme je l'ai mentionné la dernière fois, la moitié est un surplus non carré, alors j'arrondis à partir de 2 $.

La raison pour laquelle nous ne commençons pas par $ 1 $ est que $ x $, qui est $ x ^ 2 \ equiv 1 \ {\ rm mod} p , existe de toute évidence ( x = 1 $) pour tout $ p $. Parce que 1 $ est un excédent carré.

`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}

Cela reste le même. Comme précédemment, définissez-le en minuscules.

`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.

Si $ t_i \ equiv 1 $, alors $ \ pm R_i $ est la racine carrée de $ n $ et quitte l'instruction de boucle.
Sinon, mettez à jour la valeur comme suit:

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

Maintenant, il y a deux explications supplémentaires pour mettre cela en œuvre.

Le premier.

Lors de la recherche de $ M_ {i + 1} $, il est divisé en $ j = 1, 2, \ cdots $ dans l'ordre, mais "$ t_i $ est multiplié par $ 2 $ fois et $ (t_i) ^ 2 $ Sinon, multipliez $ t_i $ par $ 4 $ pour calculer $ (t_i) ^ 4 $ et vérifiez si cela devient 1. Le code suivant est un peu inutile. Tu ne penses pas qu'il y en a beaucoup? (M_update correspond à $ M_ {i + 1} $)

`python`


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

Si vous avez calculé $ (t_i) ^ 2 $, vous pouvez le mettre au carré pour obtenir $ (t_i) ^ 4 $, alors réutilisons-le [^ 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)

La deuxième.

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

Si vous définissez, la mise à jour de la valeur peut être clairement écrite comme suit. Ce symbole peut également être trouvé dans Wikipedia.

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

La dernière fois, j'ai pensé qu'il serait déroutant d'introduire plus de variables, alors je l'ai omis.

Sur la base des deux points ci-dessus, vous pouvez écrire le code comme suit.

`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

        #Confirmation de réponse
        check_sqrt(r, n, p)
        return [r, p - r]

Comme note de mise en œuvre, utilisez à la fois $ M_i $ et $ M_ {i + 1} $ lors de la mise à jour vers $ c_ {i + 1}, t_ {i + 1}, R_ {i + 1} $ Donc, une fois que vous avez défini m_update = j, ne mettez pas à jour m immédiatement.

Autre

Il est en fait possible de vérifier si $ p $ est un nombre premier en temps polynomial [^ 4].

`python`


from gmpy2 import is_prime

is_prime(p)

`python`


from Crypto.Util.number import isPrime

isPrime(p)

Un jugement des nombres premiers à grande vitesse est possible.

Je pense que les deux sont des modules qui ne sont pas inclus par défaut, vous devez donc les installer avec pip3.

Code source complet

`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]: Si une solution est trouvée avec $ 0 <x <p $, alors ajouter (ou soustraire) $ p $ à ce $ x $ est aussi une solution naturelle, donc cette fois Limité à la plage de 0 $ <x <p $. [^ 2]: En Python, vous pouvez écrire ʻa ** b% c, mais l'utilisation de la fonction powfonctionne plus rapidement. [^ 3]: Par exemple, si $ 0 <j <10 $, le premier peut appeler la fonctionpow` jusqu'à 18 fois, tandis que le second ne peut l'appeler que 9 fois. Il s'agit d'une évaluation du montant très au sujet du calcul, mais de ce point de vue, ce dernier a été adopté cette fois. Cependant, en réalité, il n'y a presque aucune différence car l'algorithme d'origine est rapide quel que soit celui utilisé. [^ 4]: "$ p $ n'est pas un nombre premier (= un nombre composé)" et "vous pouvez voir le résultat de la factorisation première de $ p $" sont différents. Cette fois, je parle du premier. Si ce dernier est fait en temps polymorphe, la théorie de la sécurité telle que la cryptographie dite RSA sera détruite. (Cependant, il s'agit toujours d'un problème non résolu, simplement parce que l'on dit que le temps polynomial ne sera pas possible.)

[PYTHON] Comprendre et implémenter l'algorithme Tonelli-Shanks (2)

introduction

la mise en oeuvre

Symbole de Legendre

python

Quand p est un nombre premier qui est divisé par 4 et a un reste de 3

python

Lorsque p est un nombre premier qu'il reste en divisant par 4

python

python

python

python

python

python

Autre

python

python

Code source complet

python

`python`

`python`

`python`

`python`

`python`

`python`

`python`

`python`

`python`

`python`

`python`