Algorithme de Pollard p-1

Bonjour,

J'étudie cet algorithme de factorisation, mais il y a encore quelques points obscurs, notament, j'aurai aimé savoir comment peut on détecter si l'entier a choisi (au hasard) n'est pas convenable, d'apres le resultat ?
(par exemple pgcd (a^k -1, n) = n ou 1 ...)
Apparement si la borne B est insuffisante j'ai constamment un pgcd qui vaut 1... que vaut il si a n'etait pas convenable ?

En effet, il faudrai un moyen de savoir si l'echec dans la recherche d'un diviseur non trivial viens du fait que n n'est pas B-friable (cad que B n'est pas assez élevé) ou du fait que l'on a choisit un a qui ne convenait pas (car divisant p)

Merci.

Nilss

Si l'entier choisi est trop petit, le PGCD vaut 1. S'il est trop grand (supérieur ou égal au plus grand diviseur de tous les P - 1), le PGCD vaut n. Entre les deux, c'est bon !

[edit]Si a divise p, comme p divise n, donc a divise n. La factorisation est faite directement. Mais comme en général ça sert à factoriser des grands nombres, ça serait vraiment pas de pot[/edit]

Bonjour,

En fait, il y a plusieurs choses que je ne comprend pas très bien.
Je vais dejà réexposer la méthode, ce que j'en ai compris, pour que ce soit clair :)

On veut factoriser n. On fixe B.
On suppose que n possede un facteur premier p, tel que tous les facteurs premiers de p-1 sont inferieurs à l'entier B.

alors on est sur que B! est un multiple de p-1 : B! = k*(p-1)

On choisit enfin a tel que p ne divise pas a.
Donc on peut écrire le petit th de Fermat :

a^(p-1) = 1 [p] donc a^(B!) = 1 [p] et donc p | a^(B!) -1

Donc on sait que p | n et que p|a^(B!) -1 et pgcd(a^(B!) -1 , n ) donne (ou peut donner ?) un diviseur de n qui n'est pas 1 ni n.



Voila donc tout d'abord, ce que je ne comprend pas, c'est pourquoi prendre le pgcd ? est ce qu'on espere de cette manière tomber sur p par le pgcd ? (sachant que p est un diviseur des deux)
si toutes les hypotheses sont respectées (p ne divise pas a et il existe un facteur p de n tel que les facteurs premiers de p-1 sont inferieurs au B choisi) , est - on sur que cela donnera un diviseur non trivial ?

Et enfin, je me demandais aussi pourquoi un B trop grand engendre systématiquement l'echec de la méthode.
En effet, pour un B trop petit je comprend bien (à ce moment là p-1 peut ne pas etre B-lisse), mais pour B trop grand j'avoue que je ne vois pas pourquoi ça ne marcherai pas... serait ce à l'étape du PGCD qu'un B trop grand pourrait etre génant ?


Merci :)
Nilss.

Citation:

---

Envoyé par Nilss

Voila donc tout d'abord, ce que je ne comprend pas, c'est pourquoi prendre le pgcd ? est ce qu'on espere de cette manière tomber sur p par le pgcd ? (sachant que p est un diviseur des deux)
si toutes les hypotheses sont respectées (p ne divise pas a et il existe un facteur p de n tel que les facteurs premiers de p-1 sont inferieurs au B choisi) , est - on sur que cela donnera un diviseur non trivial ?

---

Peu importe sur quoi on tombe. Si on trouve un PGCD différent de 1 et de n, c'est donc un diviseur de n. Si on veut tous les diviseurs premiers, il faut à nouveau factoriser les deux diviseurs trouvés de cette manière (à moins qu'ils soient premiers, et dans ce cas l'un des deux est p).

Citation:

---

Envoyé par Nilss

Et enfin, je me demandais aussi pourquoi un B trop grand engendre systématiquement l'echec de la méthode.

---

Parce que si n a un diviseur p, il en a forcément au moins un autre (appelons-le q) tel que n = p * q. Si B est trop grand, ce qui s'applique à p s'applique aussi à q. B! sera aussi un multiple de q - 1. Le PGCD sera un multiple de p et de q, donc de p * q, en d'autres termes de n.

Merci 10_GOTO_10 :)

Si on prend le cas d'un entier RSA n = p*q avec p et q premiers,
en fait il faut que B soit tel que p soit B-lisse, mais pas q (ou inversement).

Donc en cas d'échec, on joue plutot sur la borne B que sur a (d'ailleurs c'est vrai... dans le cas d'un entier RSA, si on prend un a petit (genre 5), on est sur que p ne divisera pas a vu que p est quand meme assez conséquent).

Bon enfin tout ça c'est ce que j'ai compris :)

Nilss.