Bei einer ungeraden Primzahl $ p $ und einer ganzen Zahl $ n $ ist das nicht $ 0 $
Wenn $ x \ not \ equiv 0 $ existiert, wird $ n $ als ** quadratischer Rest ** modulo $ p $ bezeichnet, wenn kein solches $ x $ existiert. Zum Beispiel heißt $ n $ ** Quadratic Nonresidue **.
Zum Beispiel ist $ n = 2 $ ein quadratischer Rest (gelöst durch $ x = 3 $ usw.) modulo $ p = 7 $, während $ n = 3 $ ein quadratischer Nicht-Rest ist.
Nun ist es nicht so schwer zu beurteilen, ob es sich um einen quadratischen Überschuss handelt.
Definieren Sie zunächst das ** Legendre-Symbol ** unten.
Zu diesem Zeitpunkt gilt Folgendes (der Beweis ist etwas schwierig, daher werde ich ihn hier weglassen).
In der Tat, wenn $ n = 2, ist p = 7 $
Und wenn $ n = 3 ist, ist p = 7 $
ist.
In diesem Artikel werde ich darüber schreiben, wie man die Quadratwurzel $ x $ findet, wenn $ n $ ein Quadratrest ist. Im Folgenden sind, sofern nicht anders angegeben, alle $ \ equiv $ $ {\ rm mod} \ p $.
In diesem Fall ist es eigentlich einfach
Ist die Antwort. In der Tat, weil angenommen wird, dass $ n $ ein quadratischer Rest ist
Ist festgelegt,
Es wird sein. Wenn beispielsweise $ n = 2 ist, ist p = 7 $
Es wird sein.
Dies ist der ** Tonelli-Shanks-Algorithmus **, den wir dieses Mal behandeln werden.
Die Benennung von Symbolen basiert im Wesentlichen auf Wikipedia.
Step 1.
Teilen Sie $ p-1 $, bis es durch $ 2 $ geteilt wird.
($ Q $ ist eine ungerade Zahl und $ S $ ist eine positive ganze Zahl).
Step 2.
Wählen Sie nach dem Zufallsprinzip eine Zahl aus, die ** quadratisch ohne Rest ** ist, wobei Sie $ p $ als Methode verwenden, und lassen Sie sie $ z $ sein.
Ich sage "zufällig", aber da die Anzahl der quadratischen Überschüsse und quadratischen Nicht-Restbeträge zwischen $ 1 $ und $ p-1 $ jeweils die Hälfte beträgt, ist sie so klein wie $ z = 1, 2,… $. Es gibt kein Problem in Bezug auf den Berechnungsbetrag, selbst wenn Sie alle in der richtigen Reihenfolge treffen.
Darüber hinaus kann durch Verwendung des obigen Legendre-Symbols bestätigt werden, ob es sich um einen quadratischen Nicht-Rest handelt, und natürlich durch seine Definition:
ist.
Step 3.
Definieren Sie zunächst die vier Zahlen $ M_0, c_0, t_0, R_0 $ wie folgt.
Step 4.
Machen Sie eine Schleifenanweisung und einen allmählichen Ausdruck wie folgt.
Wenn $ t_i \ equiv 1 $ ist, dann ist $ \ pm R_i $ die Quadratwurzel von $ n $ und verlässt die Schleifenanweisung.
Wenn nicht, aktualisieren Sie den Wert wie folgt:
… Es wurde schwer, sofort zu sehen.
Was bedeutet "Wenn $ t_i \ equiv 1 $ ist, dann ist $ \ pm R_i $ die Quadratwurzel von $ n $"?
Ist es nicht eine Endlosschleife?
Ich möchte tatsächlich codieren und verschieben / mir ein Beispiel zeigen
Ich denke, es gibt solche Dinge, aber ich werde sie der Reihe nach erklären.
Wir haben eine Reihe von schrittweisen Formeln aufgestellt, aber in Wirklichkeit gilt Folgendes unabhängig vom Wert von $ i $.
Wir werden die Reihenfolge mit der mathematischen Reduktionsmethode überprüfen.
Zeigt an. Erstens, wenn $ i = 0 $
Hier ist ab Schritt 1 $ \ frac {p-1} {2} = Q \ cdot 2 ^ {S-1} $, also
Dies entspricht $ -1 $, wie in Schritt 2 definiert.
Als nächstes zeigen wir, dass es für $ i + 1 $ gilt, vorausgesetzt, es gilt für $ i $.
Und da angenommen wird, dass es für $ i $ gilt, ist dies auch $ -1 $.
Zeigt an. $ i = 0 $, aber genau wie beim ersten Mal
Dies entspricht $ 1 $ aus der Definition des Legendre-Symbols, da angenommen wird, dass $ n $ ein quadratischer Rest ist.
Als nächstes, ungefähr $ i + 1 $, ist dies ein etwas komplizierter Beweis.
Achten Sie nun auf $ \ left (t_ {i} \ right) ^ {2 ^ {M_ {i + 1} -1}} $.
Wenn dies quadriert wird, wird es zu $ \ left (t_ {i} \ right) ^ {2 ^ {M_ {i + 1}}} $, was $ 1 $ aus der Definition von $ M_ {i + 1} $ in Schritt 4 ist. Wird gleich sein.
Also, was ist die Zahl, die auf $ 1 $ quadriert? Apropos, es gibt natürlich nur $ 1, -1 $, $ 2 $ [^ 2].
Diesmal ist es jedoch nicht $ \ left (t_ {i} \ right) ^ {2 ^ {M_ {i + 1} -1}} \ equiv 1
Ist definiert als $ M_ {i + 1}
Daher wird es $ \ left (t_ {i} \ right) ^ {2 ^ {M_ {i + 1} -1}} \ equiv -1 $.
Außerdem wurde gerade festgestellt, dass $ \ left (c_ {i} \ right) ^ {2 ^ {M_i -1}} $ aus dem $ 1 $ -ten Ausdruck $ -1 $ ist.
Es wird sein.
Zeigt an. Wenn $ i = 0 $
Auch im Fall von $ i + 1 $
Es gilt für $ i $, dh es wird $ \ left (R_i \ right) ^ 2 \ equiv t_i \ cdot n $ angenommen.
Per Definition ist $ t_ {i + 1} = t_i \ cdot \ left (c_i \ right) ^ {2 ^ {M_i --M_ {i + 1}}} $
Sie haben alle $ 3 $ -Ausdrücke bewiesen.
Zuerst
Was bedeutet "Wenn $ t_i \ equiv 1 $ ist, dann ist $ \ pm R_i $ die Quadratwurzel von $ n $"?
Ich werde aus erklären. Das heißt, die $ 3 $ der oben gezeigten Formel
Es ist klar, wenn Sie es betrachten. Mit anderen Worten, wenn Sie $ t_i $ aktualisieren und es irgendwann zu $ t_i \ equiv 1 $ wird, lautet die obige Formel
Hat die gleiche Bedeutung wie.
Nächster,
Wird es eine Endlosschleife sein?
ist. Mit anderen Worten, es kann kein $ i $ geben, so dass $ t_i = 1 $ ist.
Dazu müssen wir zunächst die monotone Abnahme von $ M_i $ erklären. $ M_ {i + 1} $
$ \ left (t_i \ right) ^ {2 ^ {j}} \ equiv Das Minimum j, das 1 erfüllt, aber 0 <j <M_i $
Gibt es überhaupt ein solches $ j $ in $ 0 <j <M_i $?
In der Tat, ungefähr zu diesem Zeitpunkt, das $ 2 $ -te der oben gezeigten Formeln
Garantien. Mit anderen Worten, ich suchte nach $ j = 1, 2,… $, und selbst wenn ich Pech hatte und es $ \ left (t_i \ right) war ^ {2 ^ {j}} \ not \ equiv 1 $, $ j Wenn = M_i -1 $, wird es $ \ left (t_i \ right) ^ {2 ^ {j}} \ equiv 1 $ und erfüllt die Bedingung als $ M_ {i + 1} $.
Daher ist $ M_ {i + 1} $ immer kleiner als $ M_i -1 $ (es ist schwer zu verstehen, weil es einen Index gibt ...).
Jetzt können wir die monotone Abnahme von $ M_i $ sagen, und eines Tages wird es $ M_ {end} = 1 $ sein.
Zu diesem Zeitpunkt $ 2 $ der oben gezeigten Formel
Mit
Jetzt, da der Wert von $ t $ $ 1 $ ist, werden wir nicht mehr auf unbestimmte Zeit wiederholt.
Das Beispiel von Wikipedia wird so genommen, wie es ist.
Finden Sie $ x $ ($ n = 5, p = 41 $). Verwenden Sie zunächst das Legendre-Symbol
Und stellen Sie sicher, dass $ 5 $ ein quadratischer Überschuss ist.
Step 1.
Sei $ p-1 = Q \ cdot 2 ^ S $, dh $ 41-1 = 5 \ cdot 2 ^ 3 $. $ Q = 5, S = 3 $.
Step 2.
Wählen Sie die Zahl $ z $, die das Quadrat ohne Rest ist. Bei Verwendung des Legendre-Symbols ist $ 1, 2 $ ein quadratischer Rest, $ 3 $ jedoch
Und da es sich um einen quadratischen Nicht-Rest handelt, sei $ z = 3 $.
Step 3.
Mit anderen Worten
Step 4.
Von hier aus betreten Sie die Schleife, bis $ t_i = 1 $.
Wenn $ i = 0 $
Wenn $ i = 1 $
Da $ t_2 = 1 $ ist, lautet die Antwort $ \ pm R_2 = 28, 13 $.
Tatsächlich gilt $ 13 ^ 2 \ equiv 28 ^ 2 \ equiv 5 \ {\ rm mod} \ 41 $.
Es ist lang geworden, also werde ich es an [hier] weiterleiten (https://qiita.com/taiyaki8926/items/6720a1c19e9c9afbfd12).
[^ 1]: Ein einfacher Beweis ist $ i ^ 2 \ equiv (pi) ^ 2 $, daher gibt es viele Variationen von Quadraten, die Quadrate von Zahlen von $ 1 $ bis $ p-1 $ sind. Es gibt auch $ \ frac {p-1} {2} $ Stücke. Obwohl ich "höchstens" sage, gibt es keine andere Vervielfältigung. Dies kann durch die absurde Methode unter der Annahme von $ i ^ 2 \ equiv (i + k) ^ 2 $ gezeigt werden.
[^ 2]: Es gilt nur für die Primzahl $ p $. Für zusammengesetzte Zahlen gilt $ x ^ 2 \ equiv 1 \ {\ rm mod} \ 24 $, dh $ x $, $ x = 1 $ und $ x = -1 \ equiv 23 $ sowie $ x = 5 $ usw. Es wird berücksichtigt. Der Grund, warum nur $ x = \ pm 1 $ mit der Primzahl $ p $ gelöst werden kann, kann leicht durch Faktorisierung von $ x ^ 2-1 $ bewiesen werden.
Recommended Posts