Confus sur Miller-Rabin

Question

En guise d'exercice pour moi-même, je suis mise en œuvre du test de Miller-Rabin. (Travail par SICP). Je comprends le petit théorème de Fermat et a pu mettre en œuvre avec succès que. La partie que je suis en train de trébucher dans le test Miller-Rabin est cette affaire « 1 mod n ». N'est pas 1 mod n (n étant un entier aléatoire) toujours 1? Donc, je suis confus à ce qu'est une « racine carrée de 1 modulo triviale n » pourrait être puisque dans mon esprit « 1 mod n » est toujours 1 lorsque des valeurs entières. Qu'est-ce que je manque?

Answer 1

1 est congru à 9 mod 8, de sorte 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 l'ensemble de tous les numéros x tels que x est conforme à m mod n. Toute chose qui sqaures à tout élément de cet ensemble est une racine carrée de m modulo n.

donné une n, nous avons l'ensemble des entiers modulo n qui nous pouvons écrire comme Zn. c'est l'ensemble (de jeux) [1]n, [2]n, ..., [n]n. Tous les mensonges entier dans un seul et une seule 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 (élément n de) [b]n de telle sorte 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 « notation abusons » comme disent les mathématiciens.

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

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

Answer 2

C'est pourquoi le libellé était une racine carrée non négligeable 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 congru à 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 seuls racines. Cependant, pour n composite 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:

  

a « 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 devrait dire:

  

dont le carré est congruent à 1 modulo n