Démonstration Miller-Rabin

[melin]

Bonjour,
En étudiant le test de primalité de Miller-Rabin (lors d'un chiffrement RSA), on a fait une démonstration en cours:

Le prof a alors dit que : pouvait avoir pour solutions , mais également et .
Je suis d'accord pour et , mais je ne vois pas ce que pourrait être et .
Pouvez-vous m'aider?
Merci

[Ben314]

Salut,
Je comprend pas grand chose à ton truc (en particulier le modulo qui devient un modulo et ce qu'est sensé représenter tes et avec des +) et je trouve que c'est plus que archi piège à con de manipuler des racines carrées avec des congruences sans préciser on ne peut plus clairement le sens qu'on leur donne (sans parler que tout ce qui est "symboles multivoques", c'est une source colossales d’erreurs).

Enfin, bref, si ton problème c'est de déterminer les solutions de l'équation x^2 = 1 modulo n, où n est un entier quelconque, alors effectivement, il peut y en avoir plus de 2. Par exemple il est bien connu que le carré de tout impair est congru à 1 modulo 8 donc il y a 4 solutions modulo 8 (et tu vérifiera que par exemple modulo 60, il y a 8 solutions : 1 , 11 , 19 , 29 , 31 , 41 , 49 , 59 ).
Par contre, modulo un nombre premier, il n'y a que deux solutions vu que x^2=1 <=> (x-1)(x+1)=0 et comme Z/pZ est intègre, les seules solutions sont x=+1 et x=-1.

[melin]

Merci de répondre Ben314,
Je me suis effectivement trompée pour le , c'est corrigé dans le post original.

Mon prof nous avait bien précisé qu'il existait 2 autres solutions en plus de +- 1

J'ai trouvé dans mon cours que:
Les 2 autres solutions pourraient donc être: et
Est-ce que cela fait du sens?

[Ben314]

Pas tellement, non.
Quand on résout une équation polynomiale modulo n, on donne les solutions, et en particulier leur nombre modulo n. Donc par exemple, modulo 5, l'équation x^2=1 admet deux solutions qui sont x=1 modulo 5 et x=4 modulo 5. Et "les autres" solutions que tu propose, à savoir -4 et -1, c'est les mêmes vu que -4=1 mod 5 et que -1=4 mod 5. Et d'un autre coté, si on regardait le nombre de solutions dans Z (et pas modulo 5), alors il y en aurait évidement une infinité : . . . -14 ; -11 ; -9 ; -6 ; -4 ; -1 ; 1 ; 4 ; 6 ; 9 ; 11 ; 14 ; . . .
Bref, quelque soit la façon de les compter, des solutions de x^2=1 modulo p, tu en a jamais 4 : c'est soit 2 (modulo p) soit une infinité (dans Z).