Discussion:Algorithme rho de Pollard

Dans la partie "Définition formelle",

on peut lire: Ceci voudrait dire que le pgcd(xa − xb, p) = p. Comme nous ne connaissons pas p, nous effectuons ces comparaisons et ces calculs modulo n.

Ca ne serait pas plutôt : pgcd(xa − xb, n) = p ???

— Le message qui précède, non signé, a été déposé par un utilisateur sous l’IP 121.31.52.78 (discuter), le 21/6/88.

Le texte est correct. Au lieu d'écrire Ceci voudrait dire on aurait pu écrire plus formellement l'équivalence suivante:

$x_{a}\equiv x_{b}{\pmod {p}}\Leftrightarrow pgcd(x_{a}-x_{b},p)=p$

Par la suite, il explique que comme $p$ n'est pas connu, il faudra utiliser le fait que $pgcd(x_{a}-x_{b},n)=p$ puisque $n=kp,k\in \mathbb {N^{*}}$

— Le message qui précède, non signé, a été déposé par N3ige (discuter), le 25/6/9.

La partie "Définition formelle" me semble présenter plusieurs incohérences. D'abord $f$ n'est pas une fonction aléatoire au sens mathématique du terme (cf le livre de Blanc-Lapierre et Fortet) mais bien plutot "une fonction quelconque, par exemple choisie au hasard". Ensuite $S$ n'est pas un ensemble quelconque puisqu'il contient $x_0 = 2$.

Je proposerais donc la rédaction suivante:

Soit $n$ un entier dont il s'agit de rechercher un facteur. On pose $S = \left[ 0, n-1 \right] $ et l'on choisit une fonction quelconque de $S$ dans $S$, nous verrons plus tard quelles fonctions permettent un travail efficace.

— Le message qui précède, non signé, a été déposé par un utilisateur sous l’IP 176.179.202.168 (discuter), le 31/3/14.

beaucoup d'erreurs dans l'article, je crois

Acx01b (discuter) 5 octobre 2014 à 19:10 (CEST)

Problème d'ordre entre choix de f et l'exemple

L'exemple nous dit qu'on peut obtenir 83 comme facteur avec d'autres valeurs de c, mais cet exemple apparaît avant la section "choix de f", qui est celle qui introduit c. On pourrait peut-être placer "choix de f" dans la section "algorithme", entre le pseudo code et le code python ? TFSIF (discuter) 28 mai 2024 à 09:48 (CEST)