Comprendre et implémenter l'algorithme Tonelli-Shanks (1)

introduction

Étant donné un nombre premier impair $ p $ et un entier $ n $ qui n'est pas $ 0 $

x^2 \equiv n\ {\rm mod}\ p

Si $ x \ not \ equiv 0 $ existe, alors $ n $ est dit ** Résidu Quadratique ** modulo $ p $, si aucun $ x $ n'existe. Par exemple, $ n $ est dit ** Quadratic Nonresidue **.

Par exemple, $ n = 2 $ est un reste carré (résolu par $ x = 3 $, etc.) modulo $ p = 7 $, tandis que $ n = 3 $ est un carré non-reste.

Maintenant, il n'est pas si difficile de juger s'il s'agit d'un excédent carré.

Définissez d'abord le ** symbole Legendre ** ci-dessous.

\left(\begin{array} nn\\\ p \end{array}\right) := n^{\frac{p-1}{2}}

À ce stade, ce qui suit est vrai (la preuve est un peu difficile, je vais donc l'omettre ici).

\left(\begin{array} nn\\\ p \end{array}\right) \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}

En fait, si $ n = 2, p = 7 $

\left(\begin{array} nn\\\ p \end{array}\right) = 2^{\frac{7-1}{2}} = 8 \equiv 1\ {\rm mod}\ 7

Et si $ n = 3, p = 7 $

\left(\begin{array} nn\\\ p \end{array}\right) = 3^{\frac{7-1}{2}} = 27 \equiv -1\ {\rm mod}\ 7

est.

Dans cet article, j'écrirai sur la façon de trouver la racine carrée $ x $ lorsque $ n $ s'avère être un reste carré. Ci-dessous, sauf indication contraire, tous les $ \ equiv $ sont $ {\ rm mod} \ p $.

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

Dans ce cas, c'est vraiment facile

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

Est la réponse. En fait, car on suppose que $ n $ est un reste carré

\left(\begin{array} nn\\\ p \end{array}\right) = n^{\frac{p-1}{2}} \equiv 1

Est établi,

x^2 = n^{\frac{p+1}{2}} = n^{\frac{p-1}{2}} \cdot n \equiv n

Ce sera. Par exemple, si $ n = 2, p = 7 $

x = \pm 2^{\frac{7+1}{4}} = \pm 4 \equiv 3, 4\ {\rm mod}\ 7

Ce sera.

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

C'est l'algorithme ** Tonelli-Shanks ** que nous allons aborder cette fois.

La dénomination des symboles est essentiellement basée sur Wikipedia.

Step 1.

Divisez $ p-1 $ jusqu'à ce qu'il divise par 2 $ $,

p-1 = Q \cdot 2^S

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

Step 2.

Sélectionnez au hasard un nombre qui est ** carré non-reste ** en utilisant $ p $ comme méthode, et laissez-le être $ z $.

Je dis "au hasard", mais comme le nombre de carrés excédentaires et non-restants carrés est de moitié chacun entre 1 $ $ et $ p-1 $, il est aussi petit que $ z = 1, 2,… $. Il n'y a pas de problème en termes de montant de calcul même si vous appuyez sur tout dans l'ordre.

De plus, il peut être confirmé en utilisant le symbole Legendre ci-dessus s'il s'agit d'un carré non-reste, et bien sûr par sa définition,

z^{\frac{p-1}{2}} \equiv -1

est.

Step 3.

Tout d'abord, définissez les quatre nombres $ M_0, c_0, t_0, R_0 $ comme suit.

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

Step 4.

Faites une instruction de boucle et une expression graduelle comme suit.

  1. Si $ t_i \ equiv 1 $, alors $ \ pm R_i $ est la racine carrée de $ n $ et quitte l'instruction de boucle.

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

… C'est devenu difficile à voir à la fois.

Je pense qu'il y a de telles choses, mais je vais les expliquer dans l'ordre.

Préparation

Nous avons mis en place un certain nombre de formules graduelles, mais en réalité, ce qui suit est valable quelle que soit la valeur de $ i $.

\begin{cases} \left(c_i\right)^{2^{M_i -1}} \equiv -1\\\ \\\ \left(t_i\right)^{2^{M_i -1}} \equiv 1\\\ \\\ \left(R_i\right)^2 \equiv t_i \cdot n \end{cases}

Nous vérifierons dans l'ordre en utilisant la méthode de réduction mathématique.

Première formule

\left(c_i\right)^{2^{M_i -1}} \equiv -1

Indique. Premièrement, si $ i = 0 $

\left(c_0\right)^{2^{M_0 -1}} = \left(z^Q\right)^{2^{S -1}} = z^{Q \cdot 2^{S -1}}

Ici, à partir de l'étape 1, $ \ frac {p-1} {2} = Q \ cdot 2 ^ {S-1} $, donc

z^{Q \cdot 2^{S -1}} = z^\frac{p-1}{2}

Ceci est égal à $ -1 $ tel que défini à l'étape 2.

Ensuite, nous montrons qu'il vaut pour $ i + 1 $, en supposant qu'il vaut pour $ i $.

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

Et comme on suppose que cela vaut pour $ i $, cela vaut également -1 $.

Deuxième formule

\left(t_i\right)^{2^{M_i -1}} \equiv 1

Indique. $ i = 0 $, mais comme la première fois

\left(t_0\right)^{2^{M_0 -1}} = \left(n^Q\right)^{2^{S-1}} = n^{Q \cdot 2^{S-1}} = n^\frac{p-1}{2}

Ceci est égal à $ 1 $ d'après la définition du symbole de Legendre, car on suppose que $ n $ est un reste carré.

Ensuite, environ $ i + 1 $, c'est une preuve un peu compliquée.

\left(t_{i+1}\right)^{2^{M_{i+1} -1}} = \left(t_i \cdot \left(c_i\right)^{2^{M_i - M_{i+1}}}\right)^{2^{M_{i+1} -1}} = \left(t_{i}\right)^{2^{M_{i+1} -1}} \cdot \left(c_{i}\right)^{2^{M_i -1}}

Maintenant, faites attention à $ \ left (t_ {i} \ right) ^ {2 ^ {M_ {i + 1} -1}} $.

Lorsqu'il est au carré, il devient $ \ left (t_ {i} \ right) ^ {2 ^ {M_ {i + 1}}} $, qui est $ 1 $ de la définition de $ M_ {i + 1} $ à l'étape 4. Sera égal à.

Alors, quel est le nombre qui correspond à 1 $? En parlant de cela, bien sûr, il n'y a que $ 1, -1 $, $ 2 $ [^ 2].

Cependant, cette fois, ce ne sera pas $ \ left (t_ {i} \ right) ^ {2 ^ {M_ {i + 1} -1}} \ equiv 1 … ( \ ast $). Parce que, si cela est vrai, "Étape 4.

\ left (t_i \ right) ^ {2 ^ {j}} \ equiv 1 Minimum j

Est défini comme $ M_ {i + 1} , mais la formule ci-dessus ( \ ast $) est valable même avec $ j = M_ {i + 1} -1 $. " Parce que cela se produira.

Par conséquent, il devient $ \ left (t_ {i} \ right) ^ {2 ^ {M_ {i + 1} -1}} \ equiv -1 $.

De plus, $ \ left (c_ {i} \ right) ^ {2 ^ {M_i -1}} $ vient d'être prouvé être $ -1 $ à partir de l'expression $ 1 $ th, donc en conséquence,

\left(t_{i}\right)^{2^{M_{i+1} -1}} \cdot \left(c_{i}\right)^{2^{M_i -1}} \equiv (-1) \cdot (-1) = 1

Ce sera.

Troisième formule

\left(R_i\right)^2 \equiv t_i \cdot n

Indique. Si $ i = 0 $

\left(R_0\right)^2 = \left(n^{\frac{Q+1}{2}}\right)^2 = n^{Q+1} = n^Q\cdot n = t_0 \cdot n

Aussi, dans le cas de $ i + 1 $

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

Il est valable pour $ i $, c'est-à-dire qu'il suppose $ \ left (R_i \ right) ^ 2 \ equiv t_i \ cdot n $.

\left(R_i\right)^2 \cdot \left(c_i\right)^{2^{M_i - M_{i+1}}} \equiv t_i \cdot n \cdot \left(c_i\right)^{2^{M_i - M_{i+1}}}

Par définition, $ t_ {i + 1} = t_i \ cdot \ left (c_i \ right) ^ {2 ^ {M_i --M_ {i + 1}}} $

t_i \cdot n \cdot \left(c_i\right)^{2^{M_i - M_{i+1}}} = t_{i+1} \cdot n

Vous avez prouvé toutes les expressions $ 3 $.

Résolvez chaque question

Premier

Que signifie "Si $ t_i \ equiv 1 $, alors $ \ pm R_i $ est la racine carrée de $ n $"?

Je vais expliquer à partir de. Cela dit, les 3 $ th de la formule ci-dessus

\left(R_i\right)^2 \equiv t_i \cdot n

C'est clair si vous le regardez. En d'autres termes, si $ t_i $ est mis à jour et qu'il devient $ t_i \ equiv 1 $ à un moment donné, la formule ci-dessus sera à ce point.

\left(R_i\right)^2 \equiv n

A la même signification que.

prochain,

Sera-ce une boucle infinie?

est. En d'autres termes, il peut ne pas y avoir de $ i $ tel que $ t_i = 1 $.

Pour ce faire, nous devons d'abord expliquer la diminution monotone de $ M_i $. $ M_ {i + 1} $

$ \ left (t_i \ right) ^ {2 ^ {j}} \ equiv Le minimum j qui satisfait 1, mais 0 <j <M_i $

Existe-t-il vraiment un tel $ j $ dans $ 0 <j <M_i $ en premier lieu?

En fait, c'est la formule de 2 $ ème présentée ci-dessus.

\left(t_i\right)^{2^{M_i -1}} \equiv 1

Garanties. En d'autres termes, j'ai cherché $ j = 1, 2,… $, et même si je n'avais pas de chance et que c'était $ \ left (t_i \ right) ^ {2 ^ {j}} \ not \ equiv 1 $, $ j Quand = M_i -1 $, il devient $ \ left (t_i \ right) ^ {2 ^ {j}} \ equiv 1 $ et satisfait la condition comme $ M_ {i + 1} $.

Donc, $ M_ {i + 1} $ est toujours inférieur à $ M_i -1 $ (c'est difficile à comprendre car il y a un indice ...).

M_{i+1} \leq M_i -1 < M_i

Maintenant, nous pouvons dire la diminution monotone de $ M_i $, et un jour ce sera $ M_ {end} = 1 $.

Pour le moment, 2 $ de la formule ci-dessus

\left(t_i\right)^{2^{M_i -1}} \equiv 1

Avec

\left(t_{end}\right)^{2^{M_{end} -1}} \equiv 1 \Rightarrow t_{end} \equiv 1

Maintenant que la valeur de $ t $ est de 1 $, nous ne bouclons plus indéfiniment.

Exemple

L'exemple de Wikipedia est pris tel quel.

x^2 \equiv 5 \ {\rm mod}\ 41

Trouvez $ x $ ($ n = 5, p = 41 $). Premièrement, en utilisant le symbole Legendre

\left(\begin{array} 55\\\ 41 \end{array}\right) = 5^{\frac{41-1}{2}} = 5^{20} \equiv 1\ {\rm mod}\ 41

Et assurez-vous que 5 $ est un excédent carré.

Step 1.

Soit $ p-1 = Q \ cdot 2 ^ S $, soit $ 41-1 = 5 \ cdot 2 ^ 3 $. $ Q = 5, S = 3 $.

Step 2.

Choisissez le nombre $ z $ qui est le carré non-reste. En utilisant le symbole Legendre, $ 1, 2 $ est un reste carré, mais $ 3 $ est

\left(\begin{array} 33\\\ 41 \end{array}\right) = 3^{\frac{41-1}{2}} = 3^{20} \equiv -1\ {\rm mod}\ 41

Et comme il s'agit d'un carré non-reste, soit $ z = 3 $.

Step 3.

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

En d'autres termes

\begin{cases} M_0 = 3\\\ c_0 = 3^5 \equiv 38\\\ t_0 = 5^5 \equiv 9\\\ R_0 = 5^{\frac{5+1}{2}} \equiv 2 \end{cases}

Step 4.

De là, entrez dans la boucle jusqu'à $ t_i = 1 $.

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

Quand $ i = 0 $

\begin{cases} M_ {1} = \ left (\ left (9 \ right) ^ {2 ^ {j}} \ equiv 1 minimum j \ right) = 2 \\\ \\\ c_{1} = \left(38\right)^{2^{3 - 2}} \equiv 9\\\ \\\ t_{1} = 9 \cdot \left(38\right)^{2^{3 - 2}} \equiv 40\\\ \\\ R_{1} = 2 \cdot \left(38\right)^{2^{3 - 2-1}} \equiv 35 \end{cases}

Quand $ i = 1 $

\begin{cases} M_ {2} = \ gauche (\ gauche (40 \ droite) ^ {2 ^ {j}} \ equiv 1 minimum j \ droite) = 1 \\\ \\\ c_{2} = \left(9\right)^{2^{2 - 1}} \equiv 40\\\ \\\ t_{2} = 40 \cdot \left(9\right)^{2^{2 - 1}} \equiv 1\\\ \\\ R_{2} = 35 \cdot \left(9\right)^{2^{2 - 1-1}} \equiv 28 \end{cases}

Puisque $ t_2 = 1 $, la réponse est $ \ pm R_2 = 28, 13 $.

En fait, $ 13 ^ 2 \ equiv 28 ^ 2 \ equiv 5 \ {\ rm mod} \ 41 $ tient.

la mise en oeuvre

C'est devenu long, donc je vais le tourner vers ici.

[^ 1]: Une preuve simple est $ i ^ 2 \ equiv (pi) ^ 2 $, il existe donc de nombreuses variantes de carrés qui sont les carrés de nombres de $ 1 $ à $ p-1 $. Il y a aussi $ \ frac {p-1} {2} $ pièces. Cependant, bien que je dise «au plus», il n'y a pas d'autre duplication. Cela peut être montré par la méthode absurde en supposant $ i ^ 2 \ equiv (i + k) ^ 2 $.

[^ 2]: Cela n'est valable que pour le nombre premier $ p $. Pour les nombres composites, $ x ^ 2 \ equiv 1 \ {\ rm mod} \ 24 $, soit $ x $, $ x = 1 $ et $ x = -1 \ equiv 23 $, ainsi que $ x = 5 $, etc. Cela sera considéré. La raison pour laquelle seulement $ x = \ pm 1 $ peut être résolu avec le nombre premier $ p $ peut être facilement prouvée en factorisant $ x ^ 2-1 $.

Recommended Posts

Comprendre et implémenter l'algorithme Tonelli-Shanks (2)
Comprendre et implémenter l'algorithme Tonelli-Shanks (1)
Derrière l'algorithme de dessin graphique et Networkx
Compréhension complète des concepts de Bellmanford et Dyxtra
Méthode de division mutuelle euclidienne et méthode de division mutuelle euclidienne étendue
Comprendre Tensor (2): Shape
Algorithme de lapin et de tortue
Comprendre la signification des formules de distribution normale complexes et bizarres
Comprendre et implémenter l'algorithme Tonelli-Shanks (2)
Comprendre et implémenter l'algorithme Tonelli-Shanks (1)
GAN et VAE
[Introduction à StyleGAN] Mayuyu et l'anime ont souri ♬
GAN: DCGAN Part3 - Comprendre Wasserstein GAN
Python et DB: comprendre le curseur DBI
À propos de la compréhension du lecteur en 3 points [...]
Touchez la maquette et le talon