ミラーラビンで混乱しています
-
03-10-2019 - |
質問
私自身のための演習として、私はMiller-Rabinテストを実装しています。 (SICPを介して作業)。私はフェルマトの小さな定理を理解しており、それをうまく実装することができました。 Miller-Rabinテストでつまずいたのは、この「1 Mod N」ビジネスです。 1 mod n(nはランダムな整数である)は常に1ではありませんか?ですから、整数値を扱うとき、「1 modulo nの非些細な平方根」が私の心の中にあるので、常に1であるため、私は混乱しています。何が足りないの?
解決
1は9 mod 8と一致するため、3は1 mod 8の非些細な平方根です。
使用しているのは、個々の数字ではなく、同等のセットです。 [m]n
それは セットする すべての数字の x
そのような x
一致しています m
モッド n
. 。このセットのあらゆる要素をsqaureするものは、の平方根です m
モジュロ n
.
何も与えられます n
, 、私たちは、私たちが書くことができる一連の整数変数を持っています Zn
. 。これは(セットの)セットです [1]n
, [2]n
, ... ,[n]n
. 。すべての整数は、それらのセットの1つと1つだけにあります。このセットで追加と乗算を定義できます [a]n + [b]n = [a + b]n
同様に乗算のために。したがって、の平方根 [1]n
(のn要素)です [b]n
そのような [b*b]n = [1]n
.
しかし実際には、私たちは混同することができます m
と [m]n
通常、一意の要素を選択します。 m'
の [m]n
そのような 0 <= m' < n
私たちの「代表的な」要素として:これは私たちが通常考えているものです m mod n
. 。しかし、数学者が言うように、私たちは「表記を乱用している」ことを覚えておくことが重要です。
スキームの通訳ATMがないので、ここにいくつかの(非像)Pythonコードがあります。
>>> 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]
したがって、特に(最後の例を見る)、17は統一モジュロ9のルートです。実際、17^2 = 289および289%9 = 1 [8]9 = [17]9
と ([17]9)^2 = [1]9
他のヒント
そのため、文言は、1の些細な平方根であるためのものでした。
17は、1、mod 144の非自明な平方根です。したがって、17^2 = 289、これは1 mod 144と一致します。nがプライムの場合、1とn-1は1の2つの平方根です。そのような2つのルーツだけです。ただし、複合nの場合、一般に複数の正方形の根があります。 n = 144では、正方形の根は{1,17,55,71,73,89,127,143}です。
誤解は、本が非自明なルートについて与える定義から来ていると信じています。
「1モジュロnの非自明な平方根」、つまり、1またはn -1に等しくない数字 その正方形は1モジュロnに等しい
私がそれが言うべきだと信じているところ:
その正方形は 一致 1モジュロnに