

Next:Information
partielle sur le Up:No
TitlePrevious:Conaissance
de
Calcul de l'exposant de déchiffrement
-
La conaissance de a permet de déchiffrer
le texte !!!
-
Mais aussi de factoriser n.
Donc si a est révélé,
Bob devra changer b et a et aussi n !!!!
-
Algorithme de factorisation utilisant a
-
tire w < n aleatoire
-

-
si x < n alors succès x=p
ou x=q
-

-
écris
, r impair
-
-
si
alors fin échec
-
tant que
fais
-

-
-
si
alors fin échec
-
sinon
succès x=p ou x=q
-
Exemple: n=89855713 et b=34986517 et
a=82330933. Tirons w=5
-

-
étape 6: v=885877701
-
étape 10: v=1
-
étape 12: pgcd (85877702,n)
= 9103
-
Donc p=9103 et
-
Algorithme Las Vegas. Pourquoi ?
-
Complexité ??
-
Probabilté de succès
