algorithm - ミラーラビンで混乱

Question

私自身の演習として、ミラーラビン素検定を実装しています。（SICPを介した作業）。私はフェルマーの小定理を理解し、それをうまく実行することができました。ミラーラビン素検定で私がつまずくのは、この「1modn」ビジネスです。1 mod n（nはランダムな整数）は常に1ではありませんか？ですから、整数値を扱うとき、私の考えでは「1 mod n」は常に1であるため、「nを法とする1の自明でない平方根」が何であるかについて混乱しています。私は何が欠けていますか？

Answer 1

1 は 9 mod 8 に合同であるため、3 は 1 mod 8 の非自明な平方根です。

あなたが扱っているのは、個々の数ではなく、同値集合です。modに合同であるようなすべての数[m]nの集合です。このセットの任意の要素を 2 乗するものは、moduloの平方根です。xxmnmn

任意nの が与えられると、次のように記述できる n を法とする整数のセットが得られZnます。これは、(セットの) [1]n、[2]n、 ... 、のセットです[n]n。すべての整数は、これらのセットの 1 つだけに存在します。[a]n + [b]n = [a + b]n乗算についても同様に、このセットで加算と乗算を定義できます。したがって、の平方根[1]nは、そのような（のn要素）[b]nです[b*b]n = [1]n。

ただし、実際には、「代表的な」要素などの一意の要素と混同mし、通常は選択することができます。これは、通常、 . しかし、数学者が言うように、私たちは「表記法を乱用している」ことを心に留めておくことが重要です。[m]nm'[m]n0 <= m' < nm 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]

[8]9 = [17]9したがって、特に (最後の例を見ると)、17 は 9 を法とする 1 の根です。実際、17^2 = 289 および 289 % 9 = 1 です。([17]9)^2 = [1]9

Answer 2

そのため、1 の NONTRIVIAL 平方根を意味する言葉遣いになっています。1 は、任意の係数 n に対して、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} です。