對米勒拉賓感到困惑

作爲我自己的練習，我正在實施米勒拉賓測試。（通過SICP工作）。我理解費馬的小定理，並能夠成功實現這一點。我在Miller-Rabin測試中被絆倒的部分是這個「1 mod n」業務。不是1 mod n（n是一個隨機整數）總是1嗎？所以我很困惑，因爲在我看來，「1模n的非平凡平方根」可能是「1 mod n」在處理整數值時總是1。我錯過了什麼？對米勒拉賓感到困惑

來源

2010-09-17 Josh Infiesto

添加了[數學]標籤。 – aaronasterling 2010-09-17 07:40:32

這個問題是題外話題，因爲它不是一個編程問題 – 2014-06-04 22:50:41

1是全等至9 MOD 8 SO 3爲1國防部8

的不平凡平方根你正在使用的不是個體的數字，但同值。 [m]n是集合的所有數字x，使得x與m mod n一致。任何與此集合中任何元素相同的東西都是m的平方根模n。

給出任何n，我們有一組整數模n我們可以寫爲Zn。這是一套（套）[1]n,[2]n，...，[n]n。每個整數都位於這些集合中的一箇中。我們可以通過[a]n + [b]n = [a + b]n定義這個集合上的加法和乘法，同樣也可以用於乘法。所以[1]n的平方根是[b]n的一個（n元素），例如[b*b]n = [1]n。

但在實踐中，我們可以混爲一談m與[m]n，通常選擇的獨特元素的[m]n這樣0 <= m' < n爲我們的「代表」元素m'：這就是我們通常認爲的m mod n。但重要的是要記住，我們正像數學家所說的那樣「濫用符號」。

這裏的一些（非慣用語）Python代碼，因爲我沒有一個方案解釋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]

因此，特別是（看最後一個例子），17是統一模的根9.實際上，17^2 = 289和289％9 = 1。返回到我們以前的符號[8]9 = [17]9和([17]9)^2 = [1]9

來源

2010-09-17 07:26:14 aaronasterling

這就是爲什麼措辭是爲1的NONTRIVIAL平方根。1是1的平凡平方根，任何模數n。

17是1的非平凡平方根mod 144.因此17^2 = 289，這與1 mod 144一致。如果n是素數，則1和n-1是1，而他們是唯一兩個這樣的根。但是，對於複合n，通常有多個平方根。 n = 144時，平方根爲{1,17,55,71,73,89,127,143}。

來源

2010-09-17 09:28:52

我認爲，誤解來自定義書中給出了關於平凡根：

一個「平凡的平方根1模n」，即數不等於1或N - 1 其平方等於1個模n

在哪裏我相信它應該說：

其廣場是一致以1爲模n

來源

2014-07-26 20:22:21 sfotiadis

我和OP一樣都有同樣的困惑，而且這個解釋讓所有的不同。接受的答案很好，但是_this_答案解決了混淆的根源。 – 2017-06-21 15:55:51

對米勒拉賓感到困惑

回答

相關問題