Bối rối trên Miller-Rabin

Question

Như một bài tập cho bản thân mình, tôi đang thực hiện bài kiểm tra Miller-Rabin. (Làm việc thông qua SICP). Tôi hiểu định lý nhỏ của Fermat và có thể thực hiện thành công điều đó. Phần mà tôi đang bị trói buộc trong thử nghiệm Miller-Rabin là công việc "1 n n" này. Không phải là 1 mod n (n là một số nguyên ngẫu nhiên) luôn luôn 1? Vì vậy, tôi bối rối về những gì một "căn bậc hai nontrivial của 1 modulo n" có thể được kể từ trong tâm trí của tôi "1 mod n" luôn luôn là 1 khi giao dịch với các giá trị số nguyên. Tôi đang thiếu gì?

Answer 1

1 là đồng dư với 9 mod 8 nên 3 là một căn bậc hai tầm thường phi của 1 mod 8.

những gì bạn đang làm việc với không phải là số cá nhân, nhưng bộ tương đương. [m]n là đặt của tất cả các số x sao cho x là đồng dư với m mod n. Bất kỳ điều nào mà sqaures cho bất kỳ phần tử nào của tập hợp này đều là căn bậc hai của m modulo n.

cho bất kỳ n, chúng tôi có tập hợp các số nguyên modulo n mà chúng tôi có thể viết là Zn. đây là tập hợp (của bộ) [1]n, [2]n, ..., [n]n. Mỗi số nguyên nằm trong một và chỉ một trong số các bộ đó. chúng ta có thể định nghĩa phép cộng và nhân trên tập hợp này bằng [a]n + [b]n = [a + b]n và tương tự như vậy cho phép nhân. Vì vậy, một căn bậc hai của [1]n là một phần tử (n) [b]n sao cho [b*b]n = [1]n.

Trên thực tế, mặc dù chúng ta có thể conflate m với [m]n và thường chọn các yếu tố độc đáo, m' của [m]n mà 0 <= m' < n như yếu tố 'đại diện' của chúng tôi: đây là những gì chúng ta thường nghĩ đến như m mod n. nhưng điều quan trọng cần nhớ là chúng tôi đang 'lạm dụng ký hiệu' như các nhà toán học nói.

đây là một số (không thành ngữ) mã python như tôi không có một máy ATM chương trình thông dịch viên:

>>> 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] 

Vì vậy, đặc biệt (nhìn vào ví dụ cuối cùng), 17 là cội rễ của sự đoàn kết modulo 9. thực sự, 17^2 = 289 và 289% 9 = 1. quay trở lại ký hiệu trước đây của chúng tôi [8]9 = [17]9 và ([17]9)^2 = [1]9

Answer 2

Đó là lý do tại sao từ ngữ dành cho căn bậc hai không bình thường của 1. 1 là căn bậc hai bình thường của 1 , đối với bất kỳ mô đun n nào.

17 là một căn bậc hai không nhỏ của 1, mod 144. Như vậy 17^2 = 289, là đồng dư với 1 mod 144. Nếu n là số nguyên tố, thì 1 và n-1 là hai căn bậc hai của 1, và chúng là hai gốc rễ duy nhất. Tuy nhiên, đối với tổng hợp n, thường có nhiều rễ vuông. Với n = 144, rễ vuông là {1,17,55,71,73,89,127,143}.

Answer 3

Tôi tin rằng sự hiểu lầm xuất phát từ định nghĩa của cuốn sách cung cấp cho khoảng gốc không tầm thường:

một “tầm thường căn bậc hai của 1 modulo n”, có nghĩa là, một số không bằng 1 hoặc n - 1 mà vuông bằng 1 modulo n

đâu tôi tin rằng nó nên nói:

mà vuông là congruent to 1 modulo n