Confus sur Miller-Rabin

Question

Comme un exercice pour moi-même, j'implémente le test Miller-Rabin. (Travailler à travers SICP). Je comprends le petit théorème de Fermat et j'ai réussi à le mettre en œuvre avec succès. Le rôle que je suis en train de jouer dans le test de Miller-Rabin est celui de «1 mod n». N'est-ce pas 1 mod n (n étant un entier aléatoire) toujours 1? Donc je suis confus à ce que pourrait être une "racine carrée non triviale de 1 modulo n" puisque dans mon esprit "1 mod n" est toujours 1 lorsqu'il s'agit de valeurs entières. Qu'est-ce que je rate?

Answer 1

1 est congru à 9 mod 8 donc 3 est une racine carrée non triviale de 1 mod 8.

ce que vous travaillez avec des numéros individuels ne sont pas, mais des ensembles d'équivalence. [m]n est le défini de tous les numéros x tel que x est congruent à m mod n. Tout ce qui sqaures à un élément de cet ensemble est une racine carrée de m modulo n.

étant donné n, nous avons l'ensemble des entiers modulo n que nous pouvons écrire comme Zn. c'est l'ensemble (des ensembles) [1]n, [2]n, ..., [n]n. Chaque entier se trouve dans un et un seul de ces ensembles. nous pouvons définir l'addition et la multiplication sur cet ensemble par [a]n + [b]n = [a + b]n et de même pour la multiplication. Ainsi, une racine carrée de [1]n est un (n élément de) [b]n tel que [b*b]n = [1]n.

Dans la pratique cependant, nous pouvons amalgamer m avec [m]n et choisissez normalement l'unique élément, m' de [m]n tels que 0 <= m' < n comme notre élément « représentatif »: voilà ce que nous pensons habituellement comme m mod n. mais il est important de garder à l'esprit que nous «abusons de la notation» comme disent les mathématiciens.

est ici un code python (non idiomatiques) que je n'ai pas un interprète système 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] 

Ainsi, en particulier (regardant le dernier exemple), 17 est une racine de l'unité modulo 9. en effet, 17^2 = 289 et 289% 9 = 1. revenant à notre notation précédente [8]9 = [17]9 et ([17]9)^2 = [1]9

Answer 2

C'est pourquoi le libellé était pour une racine carrée NONTRIVIALE de 1. 1 est une racine carrée triviale de 1 , pour tout module n.

17 est une racine carrée non-triviale de 1, mod 144. Ainsi 17^2 = 289, ce qui est congruent à 1 mod 144. Si n est premier, alors 1 et n-1 sont les deux racines carrées de 1, et ils sont les deux seules racines de ce genre. Cependant, pour le composite n, il y a généralement plusieurs racines carrées. Avec n = 144, les racines carrées sont {1,17,55,71,73,89,127,143}.

Answer 3

Je crois que le malentendu vient de la définition du livre donne de la racine triviale:

une « racine carrée non triviale de 1 modulo n », qui est, un nombre non égal à 1 ou n - 1 dont le carré est égal à 1 modulo n

Là où je crois qu'il faut dire:

dont le carré est congruente à 1 modulo n