14 mars 2015

3 messages - Retourner à l'article
  • Le « problème du logarithme discret » en cryptographie

    le 14 mars 2015 à 10:55, par B !gre

    J’ai beaucoup aimé cet article ! Une petite remarque cependant : dans la partie « Notions de complexité », j’aurais mis une phrase courte pour justifier les appellations « complexité linéaire », « complexité polynomiale », etc. car au premier abord, il n’est pas évident d’appeler « linéaire » une quantité qui croit de manière logarithmique... Mentionner que cela correspond à la taille de l’écriture de $n$ peut aider.

    Répondre à ce message
  • Le « problème du logarithme discret » en cryptographie

    le 13 avril 2015 à 14:05, par Nicolas Duhamel

    Le théorème de Shoup qui est cité dans l’article est légèrement faux. Et ce à cause de la réduction de Pohlig-Hellman. En effet, la réduction étant générique, si l’ordre $n$ du groupe n’est pas premier alors on peut faire mieux que $\sqrt{n}$ en appliquant la réduction. Si on veut donc être un peu plus précis, il faudrait dire que l’on ne peut pas résoudre le problème du logarithme discret en moins de $\sqrt{p}$ opérations de groupe où $p$ est le plus grand facteur premier de $n$.

    Répondre à ce message
  • Le « problème du logarithme discret » en cryptographie

    le 13 avril 2015 à 14:23, par Christophe Delaunay

    Merci, j’ai effectivement oublié de dire n premier...

    C. Delaunay

    Répondre à ce message
Pour participer à la discussion merci de vous identifier : Si vous n'avez pas d'identifiant, vous pouvez vous inscrire.