Confuso su Miller-Rabin

Question

Come esercizio per me, sto implementando il test di Miller-Rabin. (Di lavoro attraverso SICP). Capisco piccolo teorema di Fermat ed è stato in grado di implementare con successo questo. La parte che mi sto inciampato su nel test di Miller-Rabin è questo business "1 mod n". Non è 1 mod n (n essendo qualche intero casuale) sempre 1? Così sto confuso a ciò che un "radice quadrata non banale di 1 modulo n" potrebbe essere dato nella mia mente "1 mod n" è sempre 1 quando si tratta di valori interi. Che cosa mi manca?

Answer 1

1 è congruente a 9 mod 8 in modo 3 è una radice quadrata non banale di 1 mod 8.

quello che si sta lavorando con i numeri non è individuale, ma insiemi di equivalenza. [m]n è il set di tutti i numeri x tali che x è congruente al m mod n. Qualsiasi cosa che sqaures a qualsiasi elemento di questo insieme è una radice quadrata di m modulo n.

dato alcuna n, abbiamo l'insieme degli interi modulo n cui possiamo scrivere come Zn. questo è l'insieme (di serie) [1]n, [2]n, ..., [n]n. Ogni intero si trova in uno e solo uno di questi apparecchi. possiamo definire somma e moltiplicazione su questo set da [a]n + [b]n = [a + b]n e similmente per la moltiplicazione. Quindi una radice quadrata di [1]n è un (elemento n di) [b]n tale che [b*b]n = [1]n.

In pratica, però, siamo in grado di confondere m con [m]n e normalmente scegliere l'unico elemento, m' di [m]n tale che 0 <= m' < n come il nostro elemento 'rappresentante': questo è ciò che siamo soliti pensare come il m mod n. ma è importante tenere a mente che siamo 'abusando notazione' come dicono i matematici.

Ecco alcuni (non idiomatica) codice Python come non ho uno schema di interprete 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]

Quindi, in particolare (guardando l'ultimo esempio), 17 è una radice di unità modulo 9. infatti, 17 ^ 2 = 289 e il 289% 9 = 1. Tornando al nostro precedente notazione [8]9 = [17]9 e ([17]9)^2 = [1]9

Answer 2

Questo è il motivo per il testo è stato per una radice quadrata non banale di 1. 1 è una radice quadrata banale di 1, per qualsiasi modulo n.

17 è una radice quadrata non banale di 1, mod 144. Così 17 ^ 2 = 289, che è congruente a 1 mod 144. Se n è primo, poi 1 e n-1 sono i due radici quadrate di 1 , e sono gli unici due di tali radici. Tuttavia, per compositi n sono generalmente più radici quadrate. Con n = 144, le radici quadrate sono {1,17,55,71,73,89,127,143}.

Answer 3

Credo che l'equivoco deriva dalla definizione del libro dà circa la radice non banale:

  

una “radice quadrata banale di 1 modulo n”, cioè un numero diverso da 1 o n - 1 cui quadrato è uguale a 1 modulo n

Dove credo che dovrebbe dire:

  

cui quadrato è congruente per 1 modulo n