crypto / courbes éliptiques / polynomes 3ème degré

[invite42dac78c]

Salut

Je suis nouveau sur ce forum, et je ne connais donc pas votre niveau... Vu la personne qui m'a conseillé ce forum, je ne doute pas de vos capacitées...

Je programme énormément, et j'ai besoin d'un logiciel de cryptographie puissant, j'ai pensé tout d'abbord à PGP ou GPG mais le RSA, c'est puissant si on à des autorisations spéciales ...

Les logiciels de cryoto sont "bridés" à 128 bits, j'avais commencé un logiciel qui faisait de la crypto RSA 32... Puis une librairie permetant de faire des calcs en 2048 bits... je n'ai pas réussi à combiner les deux pour deux raisons : en C, relier une lib à un programme, c'est chiant... Les convertions de types sont compliqués... et la vitesse de ma lib était plutôt peu convainquante... De plus, je n'ai jamais réussi à faire le test de Miller rabin, donc, je n'ai jamais eu de grand nombres premiers à ma disposotion...

Je cherche donc de l'aide pour les courbes éliptiques, autre méthode de cryptographie assymétrique toujours...

Je me trouve face à un "petit" problème ...

x^3 + ax^2+bx+c=0

on résoud comment ça ?? évidement je cherche x....

je demanderais surement encore votre aide par le suite.... C'est un sujet complexe...

Je donnerais les sources de mon logiciel sous licence GPL...
-----

[inviteab2b41c6]

Il y'a justement eu un post a ce sujet hier, il est encore sur la 1e page.
Tu y trouveras surement ton bonheur...

[invite4793db90]

Bonjour et bienvenue!

Quinto a raison: il y a eu un post hier. Sinon: http://villemin.gerard.free.fr/ThNbDemo/Eqa3d.htm

A propos des courbes elliptiques, tu trouveras pas mal d'infos en cherchant sous google (cryptographie, courbes elliptiques). N'hésite pas à poster si certains points te paraissent obscurs.

En passant, il existe une sorte de généralisation des courbes elliptiques, les modules de Drinfeld, qui sont assez en vogue en cryptographie en ce moment. Cependant, je serais bien embêté pour t'expliquer, car ça dépasse largement mes compétences!

Cordialement.

[invite42dac78c]

Merci bcp

Il me reste cependant quelques points à régler :

$p=
$q=

$u=racine_cube(-$q/2+sqrt($q*$q/4+$p*$p*$p/27));
$u=racine_cube(-$q/2-sqrt($q*$q/4+$p*$p*$p/27));

x1 = u + v - a/3
x2 = ( - u/2 - v/2 - a/3 ) + 1/2 i O3 ( u - v )
x3 = ( - u/2 - v/2 - a/3 ) - 1/2 i O3 ( u - v )

je mets quoi pour $p et $q ??

de plus, 1/2 iO3 c'est quoi ?
toutes ces parenthèses sont des facteurs de ?? (c'était des { sur le site...)

et sinon, on fait comment pour calculer une racine cubique d'un nombre ? Car j'ai besoin de ça pour mon programme, en php comme ne C++, on n'a pas la racine cubique d'un nombre comme ça...

[A voir en vidéo sur Futura]

[invite14ea0d5b]

Pour la racine cubique,
si tu programmes en C++, essaie pow(x,1/3) de math.h, si tu programme en php, je sais pas... mais il doit bien exister une fonction puissance aussi. C'est ptetre même pow(nombre, exposant) aussi

[invite8f53295a]

Mais si tu veux résoudre ce jour de truc pour un programme, une méthode d'approximation du genre Newton ne serait pas plus efficace ?

[invite3f53d719]

Je ne vois pas pourquoi tu as besoins de résoudre le polynome dans le cadre des courbes elliptiques. En plus, pour l'application à la cryptographie, l'équation est sur Z/nZ, (ensemble des entiers modulo n), donc bah les formules de Cardan et cie, tu peux oublier

Eric

PS: si tu veux des infos sur les courbes elliptiques et la cryptographie : http://tpe.crpyot.free.fr

[invite42dac78c]

pour ton lien : hote introuvale....

Sinon, le truc c'est que les valeurs intermétiaires doivent êtres précisest...

pour le polynome :
je doit chercher les points d'intersection de cette courbe et de cette droite :

y=ax+b

y^2=x^3+cx+d

[invite8f53295a]

Sinon, le truc c'est que les valeurs intermétiaires doivent êtres précisest...

Justement, la méthode de Newton converge extrèmement vite, et à mon avis sera plus précise que les divers arrondis induits par le calcul avec la formule de Cardan. D'ailleurs pour calculer les racines cubiques, n'utilise-t-on pas un algorithme à la Newton ?

[invite42dac78c]

expliques moi en quoi ça consiste....
je sèche complètement...

[invite8f53295a]

L'algorithme est le suivant : étant donné un polynôme à coefficients réels f(x)=x^n+a_(n-1)x^(n-1)+...+a_0 (je l'ai bien pris unitaire, il me semble que pour l'initialisation que je vais décrire c'est assez important). On prend pour valeur initiale x_0, un réel plus grand que toutes les racines réelles, je pense que sup(1,|a_0|+|a_1|+....+|a_(n-1)|) devrait convenir. On calcule ensuite la suite définie par la relation de récurrence x_(n+1)=x_(n)-f(x_(n))/f'(x_(n))
Cette suite va converger très vite une racine du polynôme.
Il me semble que sous la forme que j'ai donnée c'est juste, cependant je ne suis pas un spécialiste de la question, donc tu devrais essayer de vérifier l'initialisation ailleurs, les sites traitant de la question ne doivent pas manquer...