IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C++ Discussion :

Implémentation d'un algorithme foireuse


Sujet :

C++

  1. #1
    Membre éprouvé
    Profil pro
    Inscrit en
    Février 2007
    Messages
    217
    Détails du profil
    Informations personnelles :
    Âge : 32
    Localisation : France

    Informations forums :
    Inscription : Février 2007
    Messages : 217
    Par défaut Implémentation d'un algorithme foireuse
    Bonjour,

    Je fait un petit programme cryptant par courbe elliptique. Dans celui-ci je dois implémenter l'exponentiation rapide. C'est un algo simple mais j'ai réussi à me planter et je ne vois pas où ...
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
     
        template<typename T>
        std::pair<T, T> QuickExponentiation(T p, T a, T e, std::pair<T, T> point)
        {
            if( 1 < e)
            {
                if(p % 2 ==0)
                    return AddPoints(p, a, QuickExponentiation(p, a, e/2, point), QuickExponentiation(p, a, e/2,point));
                else
                    return AddPoints(p, a, AddPoints(p, a, QuickExponentiation(p, a, (e-1)/2,point), QuickExponentiation(p, a, (e-1)/2, point)), point);
            }
            return point;
        }
    La fonction AddPoints() fonctionne (vérifié), voici son prototye:
    template<typename T>
    std::pair< T, T> AddPoints(T p, T a, const std::pair<T, T>& firstPoint, const std::pair<T, T>& secondPoint);

    Votre aide est la bienvenue.
    Merci

  2. #2
    Membre expérimenté
    Inscrit en
    Octobre 2007
    Messages
    285
    Détails du profil
    Informations personnelles :
    Âge : 44

    Informations forums :
    Inscription : Octobre 2007
    Messages : 285
    Par défaut
    Bonjour khazna,

    Dans quelle mesure "ça ne marche pas", comment se comporte la fonction ?

    Cdt.

  3. #3
    Membre éprouvé
    Profil pro
    Inscrit en
    Février 2007
    Messages
    217
    Détails du profil
    Informations personnelles :
    Âge : 32
    Localisation : France

    Informations forums :
    Inscription : Février 2007
    Messages : 217
    Par défaut
    Par exemple, lorsque je fais:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
     
    QuickExponentiation(29, 1, 2, std::pair<int, int>(28, 12))
    ça me sort le point (7, 25) alors qu'en faisant l'addition avec AddPoints() ça me sort le bon résultat (-2, 22).
    A ne rien y comprendre

  4. #4
    Membre émérite Avatar de valefor
    Profil pro
    Inscrit en
    Décembre 2006
    Messages
    711
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2006
    Messages : 711
    Par défaut
    Ton "e / 2" est certainement passé en tant qu'entier à QuickExponentiation. C'est vraiment ce que tu veux ?

  5. #5
    Membre éprouvé
    Profil pro
    Inscrit en
    Février 2007
    Messages
    217
    Détails du profil
    Informations personnelles :
    Âge : 32
    Localisation : France

    Informations forums :
    Inscription : Février 2007
    Messages : 217
    Par défaut
    Oui, je crois

  6. #6
    Membre expérimenté
    Inscrit en
    Octobre 2007
    Messages
    285
    Détails du profil
    Informations personnelles :
    Âge : 44

    Informations forums :
    Inscription : Octobre 2007
    Messages : 285
    Par défaut
    Euh.. J'ai peut être trouvé !!!

    La fonction AddPoint prend comme paramètres des références...

    std::pair< T, T> AddPoints(T p, T a, const std::pair<T, T>& firstPoint, const std::pair<T, T>& secondPoint);

    Or tu lui envoies un retour de fonction !!!

    Utilise des variables tempons et revérifie...

  7. #7
    Membre éprouvé
    Profil pro
    Inscrit en
    Février 2007
    Messages
    217
    Détails du profil
    Informations personnelles :
    Âge : 32
    Localisation : France

    Informations forums :
    Inscription : Février 2007
    Messages : 217
    Par défaut
    C'est pas ça...
    Raahhh foutue fonction ...

  8. #8
    Rédacteur/Modérateur
    Avatar de JolyLoic
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Août 2004
    Messages
    5 463
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 50
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Août 2004
    Messages : 5 463
    Par défaut
    Sans savoir ce que sont sensés faire a, p, e (celui ci, on peut encore deviner), AddPoint ou QuickExponentiation, difficile de dire ce qui ne fonctionne pas.

    Point de perf : Pour un algorithme se disant quick, calculer deux fois la même valeur (QuickExponentiation(p, a, e/2, point)) systématiquement est étrange...
    Ma session aux Microsoft TechDays 2013 : Développer en natif avec C++11.
    Celle des Microsoft TechDays 2014 : Bonnes pratiques pour apprivoiser le C++11 avec Visual C++
    Et celle des Microsoft TechDays 2015 : Visual C++ 2015 : voyage à la découverte d'un nouveau monde
    Je donne des formations au C++ en entreprise, n'hésitez pas à me contacter.

  9. #9
    Membre expérimenté
    Inscrit en
    Octobre 2007
    Messages
    285
    Détails du profil
    Informations personnelles :
    Âge : 44

    Informations forums :
    Inscription : Octobre 2007
    Messages : 285
    Par défaut
    Que retourne exactement AddPoint ?

  10. #10
    Membre éprouvé
    Profil pro
    Inscrit en
    Février 2007
    Messages
    217
    Détails du profil
    Informations personnelles :
    Âge : 32
    Localisation : France

    Informations forums :
    Inscription : Février 2007
    Messages : 217
    Par défaut
    AddPoints retourne un point.
    En fait p est un nombre premier.
    Une courbe elliptique est définie par une équation du type y²=x^3 + ax +b
    Moi je me place dans le groupe Z/pZ(je vous passe un pdf expliquant ça).

    Pour ce qui est du Quick, en fait j'essaie déjà de le faire marcher, pour la vitesse je verrai après ...
    J'ai fait un truc naïf qui fonctionne:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
     
        template<typename T>
        std::pair<T, T> QuickExponentiation(T p, T a, T e, std::pair<T, T> point)
        {
            std::pair<T, T> tmpPoint = point;
            for(T i = 0; i < e - 1; i++)
            {
                tmpPoint = AddPoints(p, a, tmpPoint, point);
            }
            return tmpPoint;
        }
    Images attachées Images attachées

  11. #11
    Membre expérimenté
    Inscrit en
    Octobre 2007
    Messages
    285
    Détails du profil
    Informations personnelles :
    Âge : 44

    Informations forums :
    Inscription : Octobre 2007
    Messages : 285
    Par défaut
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
     
    template<typename T>
    std::pair<T, T> QuickExponentiation(T p, T a, T e, std::pair<T, T> point)
    {
            std::pair<T, T> tmpPoint;
            std::pair<T, T> tmpPoint2;
     
            if( 1 < e)
            {
                if(p % 2 ==0)
                {
                    tmpPoint = QuickExponentiation(p, a, e/2, point);
                    return AddPoints(p, a, tmpPoint , tmpPoint );
                }
                else
                {
                    tmpPoint   = QuickExponentiation(p, a,(e-1)/2, point);
                    tmpPoint2   = AddPoints(p, a, tmpPoint , tmpPoint );
                    return AddPoints(p, a, tmpPoint2 , point);
                }
            }
            return point;
    }
    Et comme ça ?

  12. #12
    Expert éminent
    Avatar de Médinoc
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Septembre 2005
    Messages
    27 394
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2005
    Messages : 27 394
    Par défaut
    Attention, indentation foireuse et trompeuse: Tu as oublié les accolades (Edit: Corrigé depuis).

    (même si dans le cas présent, ça ne change pas grand-chose, puisque la section avant le else se termine par un return)
    SVP, pas de questions techniques par MP. Surtout si je ne vous ai jamais parlé avant.

    "Aw, come on, who would be so stupid as to insert a cast to make an error go away without actually fixing the error?"
    Apparently everyone.
    -- Raymond Chen.
    Traduction obligatoire: "Oh, voyons, qui serait assez stupide pour mettre un cast pour faire disparaitre un message d'erreur sans vraiment corriger l'erreur?" - Apparemment, tout le monde. -- Raymond Chen.

  13. #13
    Membre éprouvé
    Profil pro
    Inscrit en
    Février 2007
    Messages
    217
    Détails du profil
    Informations personnelles :
    Âge : 32
    Localisation : France

    Informations forums :
    Inscription : Février 2007
    Messages : 217
    Par défaut
    Toujours pas...
    Je me demande bien pourquoi ça ne fonctionne pas: ça a l'air théoriquement juste ...

  14. #14
    Membre expérimenté
    Inscrit en
    Octobre 2007
    Messages
    285
    Détails du profil
    Informations personnelles :
    Âge : 44

    Informations forums :
    Inscription : Octobre 2007
    Messages : 285
    Par défaut
    Citation Envoyé par Médinoc Voir le message
    Attention, indentation foireuse et trompeuse: Tu as oublié les accolades.
    Mis à jour... (J'ai posté trop vite...)

  15. #15
    Membre éprouvé
    Profil pro
    Inscrit en
    Février 2007
    Messages
    217
    Détails du profil
    Informations personnelles :
    Âge : 32
    Localisation : France

    Informations forums :
    Inscription : Février 2007
    Messages : 217
    Par défaut
    Après cette après midi de prog' endiablé (bon pas toute l'aprem' non plus ) j'ai réussi à finir mon crypteur par courbe elliptique (reste plus qu'a faire un prog' genre chat qui exploite ce qui a été fait et c'est bon) .
    Néanmmoins je vais chercher à résoudre ce problème et si vous avez une piste je suis prêt à l'explorer .
    Merci pour votre aide, je l'aurais pas fini sans les membres de ce forum .

  16. #16
    Membre éprouvé
    Profil pro
    Inscrit en
    Février 2007
    Messages
    217
    Détails du profil
    Informations personnelles :
    Âge : 32
    Localisation : France

    Informations forums :
    Inscription : Février 2007
    Messages : 217
    Par défaut
    Bon je viens de relire le code et j'ai trouvé: le test avec le modulo devait être e % 2 == 0
    On a vraiment cherché trop loin

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Implémentation d'un algorithme de FFT.
    Par Mp-X. dans le forum Caml
    Réponses: 28
    Dernier message: 02/08/2009, 15h55
  2. Implémentation de l'algorithme ESPRIT
    Par elhaoud dans le forum Signal
    Réponses: 5
    Dernier message: 19/05/2008, 20h45
  3. Implémentation de l'algorithme de kmeans
    Par kevin2008 dans le forum C++
    Réponses: 0
    Dernier message: 18/04/2008, 11h29
  4. Implémentation de l'algorithme FCM en C
    Par hoolaka dans le forum Algorithmes et structures de données
    Réponses: 1
    Dernier message: 11/02/2008, 22h57
  5. Réponses: 1
    Dernier message: 07/03/2007, 09h28

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo