Étant donné un nombre premier impair $ p $ et un entier $ n $ qui n'est pas $ 0 $
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.
À ce stade, ce qui suit est vrai (la preuve est un peu difficile, je vais donc l'omettre ici).
En fait, si $ n = 2, p = 7 $
Et si $ n = 3, p = 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 $.
Dans ce cas, c'est vraiment facile
Est la réponse. En fait, car on suppose que $ n $ est un reste carré
Est établi,
Ce sera. Par exemple, si $ n = 2, p = 7 $
Ce sera.
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 $ $,
($ 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,
est.
Step 3.
Tout d'abord, définissez les quatre nombres $ M_0, c_0, t_0, R_0 $ comme suit.
Step 4.
Faites une instruction de boucle et une expression graduelle comme suit.
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:
… C'est devenu difficile à voir à la fois.
Que signifie "Si $ t_i \ equiv 1 $, alors $ \ pm R_i $ est la racine carrée de $ n $"?
N'est-ce pas une boucle infinie?
Je veux coder et déplacer / Montrez-moi un exemple
Je pense qu'il y a de telles choses, mais je vais les expliquer dans l'ordre.
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 $.
Nous vérifierons dans l'ordre en utilisant la méthode de réduction mathématique.
Indique. Premièrement, si $ i = 0 $
Ici, à partir de l'étape 1, $ \ frac {p-1} {2} = Q \ cdot 2 ^ {S-1} $, donc
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 $.
Et comme on suppose que cela vaut pour $ i $, cela vaut également -1 $.
Indique. $ i = 0 $, mais comme la première fois
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.
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
Est défini comme $ M_ {i + 1}
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,
Ce sera.
Indique. Si $ i = 0 $
Aussi, dans le cas de $ i + 1 $
Il est valable pour $ i $, c'est-à-dire qu'il suppose $ \ left (R_i \ right) ^ 2 \ equiv t_i \ cdot n $.
Par définition, $ t_ {i + 1} = t_i \ cdot \ left (c_i \ right) ^ {2 ^ {M_i --M_ {i + 1}}} $
Vous avez prouvé toutes les expressions $ 3 $.
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
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.
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.
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 ...).
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
Avec
Maintenant que la valeur de $ t $ est de 1 $, nous ne bouclons plus indéfiniment.
L'exemple de Wikipedia est pris tel quel.
Trouvez $ x $ ($ n = 5, p = 41 $). Premièrement, en utilisant le symbole Legendre
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
Et comme il s'agit d'un carré non-reste, soit $ z = 3 $.
Step 3.
En d'autres termes
Step 4.
De là, entrez dans la boucle jusqu'à $ t_i = 1 $.
Quand $ i = 0 $
Quand $ i = 1 $
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.
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