[Cryptographie/fac] Algorithme de Dixon

[Jiss]

Bonjour à tous,

Alors voila à j'ai un partiel de cryptographie lundi et il y a un algorithme que je ne comprends pas, c'est l'algorithme de Dixon....

J'ai cherché sur google et les liens que je trouve n'expliquent quasiment pas le fonctionnement de l'algorithme.

Alors voilà le principe est le suivant :

On a un nombre n et on souhaite le factoriser par des entiers premiers.
Pour cela on est munit d'une base B avec un certain nombre de chiffres (et/ou nombres).

Ce qu'on va faire c'est prendre des nombres au carré et les factoriser par les éléments de la base.

Après il y a toute une démarche avec matrice et vecteur du noyau que je vous épargne pour le moment. Si vous voulez plus de détails n'hésitez pas....


QUESTION :
------------------
Le seul truc c'est que dans mon cours c'est pas expliqué d'où viennent ces nombres au carré, comment on les trouve ? On les prend au hasard ou il y a un moyen de les déterminer ?


Exemple :
-------------

n = 143
B = {2, 3, 5}

On voit que :

14² = 196 mod 143 = 53
15² = 82 mod 143
17² = 3 mod 143
19² = 3 * 5²
21² = 3 * 2²


On a donc la matrice Eij :

17 19 21
2 (0 0 2)
3 (1 1 1) = Eij
5 (0 2 0)

(On a rempli avec les exposants)

De là on en déduit la matrice Eij barre à savoir la même matrice modulo 2 :

(0 0 0)
(1 1 1) = Eij barre
(0 0 0)


Après calcul on détermine que Vj, un vecteur du noyau de Eij barre est le suivant :

(1)
(1) = Vj
(0)

On a donc x = 17 * 19 = 37 mod 143
et donc x² = 82 mod 143
(d'après le vecteur Vj)

On a trouvé x, maintenant calculons y :

--------------------------------------------------


On calcul Vj * Eij et on obtient :

(0)
(2)
(2)

Ce qui nous permet de calculer y = p1^(0/2) * p2^(2/2) * p3^(2/2)
avec p1, p2, p3 éléments de la base.

On a donc y = 3 * 5 = 15 mod 143


ON A DONC :

PGCD(x-y, 143) = PGCD(37-15, 143) = PGCD(22, 143) qui par l'algorithme d'Euclide nous donne 11


DONC n = 143 peut se factoriser par 11 on obtient donc 143 = 11 * 13



Voilou et dans cet exemple je ne sais pas en fait d'où viennent les nombres qu'on prend au début là (14², 15² etc....)


Si quelqu'un pouvait éclairer ma lanterne... :(


MERCI BEAUCOUP!!

[skilveg]

Il me semble qu'on en tire au sort et qu'on ne garde que ceux qui sont B-friables (factorisables par des nombres premiers de la base B).

Si quelqu'un peut infirmer ou confirmer...

[Jiss]

Oui j'ai l'impression qu'on tire au sort aussi.

Merci pour cette réponse, je crois que ça marche, je vais essayer avec d'autres exemples :)