Discussion :

[khazna]

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

[JeromeBcx]

Bonjour khazna,

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

Cdt.

[khazna]

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

[valefor]

Ton "e / 2" est certainement passé en tant qu'entier à QuickExponentiation. C'est vraiment ce que tu veux ?

[khazna]

Oui, je crois

[JeromeBcx]

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

[khazna]

C'est pas ça...
Raahhh foutue fonction ...

[JolyLoic]

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

[JeromeBcx]

Que retourne exactement AddPoint ?

[khazna]

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;
    }

[JeromeBcx]

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 ?

[Médinoc]

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)

[khazna]

Toujours pas...
Je me demande bien pourquoi ça ne fonctionne pas: ça a l'air théoriquement juste ...

[JeromeBcx]

Attention, indentation foireuse et trompeuse: Tu as oublié les accolades.

Mis à jour... (J'ai posté trop vite...)

[khazna]

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 .

[khazna]

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