ミラーラビンで混乱しています

Question

私自身のための演習として、私はMiller-Rabinテストを実装しています。 （SICPを介して作業）。私はフェルマトの小さな定理を理解しており、それをうまく実装することができました。 Miller-Rabinテストでつまずいたのは、この「1 Mod N」ビジネスです。 1 mod n（nはランダムな整数である）は常に1ではありませんか？ですから、整数値を扱うとき、「1 modulo nの非些細な平方根」が私の心の中にあるので、常に1であるため、私は混乱しています。何が足りないの？

Answer 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

Answer 2

そのため、文言は、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}です。

Answer 3

誤解は、本が非自明なルートについて与える定義から来ていると信じています。

「1モジュロnの非自明な平方根」、つまり、1またはn -1に等しくない数字 その正方形は1モジュロnに等しい

私がそれが言うべきだと信じているところ：

その正方形は 一致 1モジュロnに