Verwirrt auf Miller-Rabin
-
03-10-2019 - |
Frage
Als Übung für mich, ich bin der Umsetzung der Miller-Rabin-Test. (Arbeits durch SICP). Ich verstehe kleinen Satz von Fermat und konnte erfolgreich das umzusetzen. Der Teil, dass ich bin immer auf dem Miller-Rabin-Test gestolpert ist dieses „1 mod n“ Geschäft. Nicht 1 mod n (wobei n eine zufällige ganze Zahl ist) immer 1? Also habe ich auf dem, was eine „nicht-triviale Quadratwurzel von 1 modulo n“ da sein könnte, in meinem Kopf „1 mod n“ verwirrt bin immer 1, wenn sie mit ganzzahligen Werten zu tun. Was bin ich?
Lösung
1 ist kongruent mod 8 bis 9 so 3 eine nicht triviale Quadratwurzel von 1 mod 8 ist.
, was Sie arbeiten mit nicht einzelnen Zahlen, sondern Äquivalenzsätze. [m]n
ist die alle Zahlen x
so dass x
ist kongruent zu m
mod n
. Jede Sache, dass sqaures auf jedes Element dieses Satzes ist eine Quadratwurzel m
Modulo n
.
gegeben jede n
, haben wir die Menge der ganzen Zahlen modulo n, die wir als Zn
schreiben. dies ist der Satz (Sätze) [1]n
, [2]n
, ..., [n]n
. Jede ganze Zahl liegt in einer und nur einer dieser Sätze. wir können zur Multiplikation mit [a]n + [b]n = [a + b]n
und ebenfalls Addition und Multiplikation auf diesen Satz definieren. So eine Quadratwurzel [1]n
ist ein (n Element), so dass [b]n
[b*b]n = [1]n
.
In der Praxis aber wir m
mit [m]n
und in der Regel wählen Sie das einzigartige Element, m'
von [m]n
so dass 0 <= m' < n
als unsere ‚Vertreter‘ Element conflate kann: das ist, was wir denken, der in der Regel als m mod n
. aber es ist wichtig, im Auge zu behalten, dass wir ‚Notation zu missbrauchen‘, wie die Mathematiker sagen.
hier einig (nicht-idiomatische) Python-Code, wie ich habe keinen Plan Interpreter ATM:
>>> def roots_of_unity(n):
... roots = []
... for i in range(n):
... if i**2 % n == 1:
... roots.append(i)
... return roots
...
>>> roots_of_unity(4)
[1, 3]
>>> roots_of_unity(8)
[1, 3, 5, 7]
>>> roots_of_unity(9)
[1, 8]
So, insbesondere (im letzten Beispiel suchen), 17 eine Einheitswurzel modulo 9 in der Tat, 17 ^ 2 = 289 und 289% 9 = 1.e Rückkehr zu unserer bisherigen Notation [8]9 = [17]9
und ([17]9)^2 = [1]9
Andere Tipps
Deshalb ist die Formulierung für eine nicht-triviale Quadratwurzel von 1 war 1 ist eine triviale Quadratwurzel von 1, für jedes Modul n.
17 ist eine nicht-triviale Quadratwurzel von 1, mod 144. Daher 17 ^ 2 = 289, die kongruent zu 1 mod ist 144. Wenn n eine Primzahl ist, dann 1 und n-1 sind die zwei Quadratwurzeln von 1 und sie sind die einzigen zwei solche Wurzeln. Doch für Verbund n gibt es im Allgemeinen mehrere Quadratwurzeln. Mit n = 144, die Quadratwurzeln sind {1,17,55,71,73,89,127,143}.
Ich glaube, dass das Missverständnis aus der Definition kommt das Buch über die nicht-triviale Wurzel gibt:
a „nicht-triviale Quadratwurzel 1 modulo n“, das heißt, nicht eine Zahl gleich 1 oder n - 1 , dessen Quadrat gleich 1 modulo n
Wo ich glaube, es sollte sagen:
dessen Quadrat kongruent , um 1 modulo n