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ù :oops:...

Code:

---

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

Bonjour khazna,

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

Cdt.

Par exemple, lorsque je fais:

Code:

---

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

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

Oui, je crois :aie:

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

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

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

Que retourne exactement AddPoint ?

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 :aie:...
J'ai fait un truc naïf qui fonctionne:

Code:

---

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

---

Code:

---

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 ?

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)

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

Citation:

---

Envoyé par Médinoc

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

---

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

Après cette après midi de prog' endiablé (bon pas toute l'aprem' non plus :aie:) 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) :yaisse2:.
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 :king:.

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