Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques AutreForum traitant des mathématiques, un peu moins scolaires CalculatricesForum sur les calculatrices [tout]Lister tous les topics de mathématiques
Niveau calculatrices
Partager :

Agorithme Rho de Pollard

Posté par imaginaire (invité) 13-05-07 à 15:26

bonjour, quelqu un pourrait m expliquer un peu le concept de cet algorithme, comment il fonctionne...

De plus, j'ai trouvé cette procédure sous maple, et je ne comprend pas trop non plus, ici on aurait 3 variables modulo N qui sont itérées mais je ne vois pas trop le fonctionnement, si qqun pouvait m'aider :

Citation :
> pollard:=proc(N)
local rnd, a, f, x, y, i, g;
rnd:=rand(N); a:=rnd(); x:=rnd(); y:=x;
for i do
x:=x^2+a mod N; y:=(y^2+a mod N)^2+a mod N; g:=igcd(y-x,N);
if g<>1 then RETURN(g,i) fi
od
end:

Posté par
perroquetre : Agorithme Rho de Pollard 13-05-07 à 16:11

Bonjour, imaginaire.

Des éléments de réponse ici:
fr.wikipedia.org/wiki/Algorithme_rho_de_Pollard

Posté par imaginaire (invité)re : Agorithme Rho de Pollard 13-05-07 à 21:05

jai deja lu..
mais ca ne ma pas trop éclairé
dans la procedure que signifient i et g ?

Posté par
robby3re : Agorithme Rho de Pollard 13-05-07 à 21:38

Salut tout les deux:
i c'est ce qu'on apelle une variable de comptage...
g c'est le pgcd je crois sous maple
si tu as maple tu peux faire ?igcd pour voir ce que c'est .

Posté par imaginaire (invité)re : Agorithme Rho de Pollard 13-05-07 à 22:25

ben en fait je ne vois "i" nul part dans l expression de x ou y ou g, c'est pour ca, je ne comprends pas dans quelle expression sont générées les valeurs de "i"

Posté par
perroquetre : Agorithme Rho de Pollard 13-05-07 à 22:33

Ta question est vraiment trop imprécise.
Que veux-tu savoir ?
Dans quel but ?
Qu'as-tu déjà compris ?

La procédure, si elle se termine, renvoie effectivement deux nombres, g et i:
g désigne un diviseur de N,
i désigne le nombre d'essais qu'il aura fallu faire avant de le déterminer.

Maintenant, s'il s'agit d'expliquer pourquoi la procédure donne un résultat correct ... il faudrait que je sache quel est ton niveau, ce que tu as déjà compris, et combien de temps tu es prêt à investir

Posté par
robby3re : Agorithme Rho de Pollard 13-05-07 à 22:35

effectivement j'avais pas vu,c'est une erreur je crois...
surtout qu'on le déclare en localnil doit apparaitre inévitablement quelque part...?
je vois pas la désolé.

Posté par
robby3re : Agorithme Rho de Pollard 13-05-07 à 22:36

Bonsoir Perroquet,effectivement,j'avais oublier que c'était cela, le nombre de fois qu'on itere c'est i...on écrit plus souvent "for i from 1 to n do..."

Posté par
perroquetre : Agorithme Rho de Pollard 13-05-07 à 22:39

sauf qu'ici, il n'y a pas de borne "n" pour i. On ne sait pas combien de temps l'algorithme va tourner

Posté par
robby3re : Agorithme Rho de Pollard 13-05-07 à 22:42

oui mais bon je pense que c'est  àcelui qui applique le programme de déterminer quelle est la limite du nombre d'itération qu'il ou elle souhaite...
aprés ça dépend de ce qu'on cherche aussi...
Bonne soirée.
A+

Posté par
perroquetre : Agorithme Rho de Pollard 13-05-07 à 22:46

Si le programmeur met sa limite trop basse, le programme pourra s'arrêter sans avoir déterminé un diviseur de N. S'il la met trop haute, le programme pourrait tourner très longtemps ...

Posté par imaginaire (invité)re : Agorithme Rho de Pollard 13-05-07 à 22:59

Citation :
Bonsoir Perroquet,effectivement,j'avais oublier que c'était cela, le nombre de fois qu'on itere c'est i...on écrit plus souvent "for i from 1 to n do..."

A daccord, je comprends mieux deja,
(je suis en L1 maths) le but de rho etant de pouvoir factoriser un nombre entier en produit de nombres premiers (unique dapres le thm fondamental de l arithmetique), je ne vois pas trop en fait comment on aboutit a ce résultat,
on a bien une fonction recursive qu on pose, (mais comment definir cette fonction ? d'apres wikipedia il sagirait d un polynome, de la forme x2 + c mod n.

en fait ma définition est la suivante :
Apr\`{e}s quoi, nous calculons par r\'{e}currence une suite $(\beta _{i} )$ en posant $$\beta _{i+1} = f(\beta_{i})$$
Les \'{e}l\'{e}ments de cette suite peuvent s'\'{e}crire sous la forme $$\beta _{i} = \gamma ^{x_{i}} \alpha ^{y_{i}}  \ \ \ i \leq 0$$
avec $x_{0}$ le nombre aléatoire initial, $y_{0} = 0$
$$ \\ x_{i+1} = \\ \left\{ \\ \begin{array}{ll} \\ x_{i} + 1 \ mod \ n & si \ \beta _{i} \in G_{1} \\ \\ 2x_{i} \ mod \ n & si \ \beta _{i}  \in G_{2} \\ \\ x_{i} & si \ \beta _{i} \in G_{3} \\ \end{array} \\ \right.\\ \\ $$
et
$$ \\ y_{i+1} = \\ \left\{ \\ \begin{array}{ll} \\ y_{i}  & si \ \beta _{i} \in G_{1} \\ \\ 2y_{i} \ mod \ n & si \ \beta _{i}  \in G_{2} \\ \\ y_{i} + 1 \ mod \ n & si \ \beta _{i} \in G_{3} \\ \end{array} \\ \right.\\ \\ $$

Posté par imaginaire (invité)re : Agorithme Rho de Pollard 13-05-07 à 22:59

la ou il y a des [?] il s'agit en fait d espaces.

Posté par imaginaire (invité)re : Agorithme Rho de Pollard 13-05-07 à 23:05

j'oubliais la definition de f dans ce cas :
Nous avons besoin de 3 sous ensembles de G, deux à deux, disjoints $G_{1},G_{2},G_{3}$ tels que $G_{1} \cup G_{2} \cup G_{3} = G$. Définissons f : G \longrightarrow G par
f(\beta ) = \\ \left\{ \\ \begin{array}{ll} \\ \gamma \beta & si \ \beta \in G_{1} \\ \\ \beta ^{2} & si \ \beta  \in G_{2} \\ \\ \alpha \beta & si \ \beta \in G_{3} \\ \end{array} \\ \right.\\ \\

Posté par
perroquetre : Agorithme Rho de Pollard 13-05-07 à 23:47

Le but de l'algorithme rho n'est pas de déterminer une décomposition en facteurs premiers de N, il est de déterminer un diviseur d'un entier N dont on sait par ailleurs qu'il n'est pas premier.

Le principe est de construire une suite récurrente u_{n+1}=f(u_n) dans Z/NZ. Comme Z/(NZ) est fini, cette suite est périodique de période k<=N à partir d'un certain rang (on "espère" en fait que cette période est bien plus petite).

Maintenant, si p est un diviseur de N, la suite v_n=u_n modulo p (qu'on ne peut pas calculer, puisqu'on ne connaît pas p) est, elle aussi, périodique de période k', avec k'<=p, et on "espère" que cette période est strictement inférieure à k.

Si v_{n+k'}=v_n modulo p, alors, x=u_{n+k'}-u_n est divisible par p et le pgcd(x,N) est multiple de p et on "espère" que ce pgcd est un diviseur strict de N.

Le problème, c'est qu'on ne peut pas stocker toutes les valeurs de u_n jusqu'à observer que q=pgcd(u_n2-u_n1,N) est différent de 1 (auquel cas la suite v_n=u_n modulo q est périodique à partir de n1 de période n2-n1). Cela prendrait trop de place em mémoire.

L'idée est qu'on conserve pendant le calcul seulement u_i et u_{2i}, et il arrivera un moment où u_i=u_{2i}. Ceci est l'idée de la procédure Maple, mais il y en a d'autres, un peu plus compliquées.

Maintenant, il y a le choix de la fonction f. Il est empirique, et on a constaté que l'ordre de grandeur de la période est égal à la racine carrée de N (ou la racine carrée de q, q étant un diviseur de N) pour le choix de cette fonction f.

Voilà le principe de l'algorithme.

Je n'ai pas compris ce que tu m'as écrit dans ton post de 22h59 (en particulier, G1,G2,G3 n'ont pas été définis). Ces questions sont très complexes (même si le programme est court), et il faut être extrêmement précis.


Rechercher
Menu
Espace membre
Changer d'île

Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :

Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !