Confuso su Miller-Rabin

Question

Come esercizio per me stesso, sto implementando il test Miller-Rabin. (Lavorando attraverso SICP). Comprendo il piccolo teorema di Fermat e sono riuscito a implementarlo con successo. La parte su cui sto lavorando nel test Miller-Rabin è questa "1 mod n". Non è 1 mod n (n è un numero intero casuale) sempre 1? Quindi sono confuso da cosa potrebbe essere una "radice quadrata non banale di 1 modulo n" poiché nella mia mente "1 mod n" è sempre 1 quando si tratta di valori interi. Cosa mi manca?

Answer 1

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

ciò che si sta lavorando non è numeri individuali, ma insiemi di equivalenza. [m]n è il set di tutti i numeri x tale che x è congruente a m mod n. Qualsiasi cosa che sqaures a qualsiasi elemento di questo set è una radice quadrata di m modulo n.

dato uno qualsiasi n, abbiamo l'insieme di interi modulo n che possiamo scrivere come Zn. questo è l'insieme (di serie) [1]n, [2]n, ..., [n]n. Ogni numero intero si trova in uno e solo uno di questi set. possiamo definire addizione e moltiplicazione su questo set di [a]n + [b]n = [a + b]n e analogamente per la moltiplicazione. Quindi una radice quadrata di [1]n è un (n elemento 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 stiamo "abusando della notazione", come dicono i matematici.

ecco qualche (non idiomatica) codice Python come io non ho un bancomat schema di interprete:

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

Così, in particolare (guardando l'ultimo esempio), 17 è una radice di unità modulo 9. anzi, 17^2 = 289 e 289% 9 = 1. ritorno alla notazione precedente [8]9 = [17]9 e ([17]9)^2 = [1]9

Answer 2

Ecco perché la dicitura era per una radice quadrata NONTRIVIAL di 1. 1 è una radice quadrata banale di 1 , per ogni modulo n.

17 è una radice quadrata non banale di 1, mod 144. Quindi 17^2 = 289, che è congruente a 1 mod 144. Se n è primo, allora 1 e n-1 sono le due radici quadrate di 1, e sono le uniche due di queste radici. Tuttavia, per il composito n esistono generalmente radici quadrate multiple. 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 non banale di 1 modulo n”, cioè un numero non uguale a 1 o n - 1 cui quadrato è uguale a 1 modulo n

Dove credo che dovrebbe fare:

cui quadrato è congruente a 1 modulo n