Répondre à la discussion
Affichage des résultats 1 à 3 sur 3

Algorithme Rho de Pollard



  1. #1
    invite67423456789

    Algorithme Rho de Pollard


    ------

    Bonjour,
    quelqu'un pourrait m'expliquer le fonctionnement de cet algorithme ? je ne le comprends pas tres bien en fait, je vois qu il marche de facon recursive, mais comment cela fonctionne avec les modulos etc.. ?
    merci

    -----

  2. #2
    invite67423456789

    Re : Algorithme Rho de Pollard

    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
    > 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:

  3. #3
    rvz

    Re : Algorithme Rho de Pollard

    Salut,

    Ca fait longtemps que je n'ai plus fait ça, donc je vais juste vous donner une bonne référence, ne me souvenant plus très précisément de l'algo et de l'idée clé qui le sous tend (pourtant c'était mon TIPE, mais c'était il y a déjà 5 ans ...)

    Donc voilà, je vous recommande Cours d'Arithmétique, de Michel Demazure. Dans mes lointains souvenirs, je crois me souvenir que le début est un peu dur, quoique très bien expliqué, et que les algo sont présentés vers le milieu du bouquin. Cela dit, le prérequis théorique n'est nécessaire que pour montrer la convergence et expliciter pourquoi cet algo est efficace.

    Bref, bonne lecture et bon courage,
    __
    rvz

Sur le même thème :

Discussions similaires

  1. Vérification pression mmHg; g et rhô ?!
    Par Alegs dans le forum Physique
    Réponses: 5
    Dernier message: 30/10/2007, 08h30
  2. Quand rho*g*h = 0 !!!!
    Par Yoh8512 dans le forum Physique
    Réponses: 2
    Dernier message: 29/10/2007, 15h52
  3. algorithme
    Par sensor dans le forum Mathématiques du supérieur
    Réponses: 4
    Dernier message: 30/11/2006, 19h14
  4. Algorithme
    Par Herbiti dans le forum Logiciel - Software - Open Source
    Réponses: 0
    Dernier message: 26/02/2006, 19h10
  5. démontrer Rho et puissance 4
    Par leg dans le forum Mathématiques du supérieur
    Réponses: 4
    Dernier message: 03/02/2006, 17h44