Comment mesurer la complexité du problème du logarithme discret?

Les réponses à cette question sur Crypto Stack Exchange disent essentiellement que, pour mesurer la complexité du problème de logarithme, nous devons prendre en compte la longueur du nombre représentant la taille du groupe. Cela semble arbitraire, pourquoi ne choisissons-nous pas la taille du groupe comme argument? Existe-t-il un critère pour savoir quel argument choisir? En fait, je sais que j'ai négligé quelque chose d'important car la complexité change énormément si nous le faisons par la taille du groupe.

time-complexity discrete-mathematics cryptography Nassim HADDAM
la source

Question interessante! Je l'ai édité pour dire "mesurer la complexité", plutôt que "le calculer", car la réponse à la façon dont nous le calculons est ¯ \ _ (ツ) _ / ¯. :-)

David Richerby

Je pense que c'est mieux ainsi. :)

Nassim HADDAM

Réponses:

$|G|$ $n$ $n \approx \log |G|$ $n$ $|G|$

$n$ $\Theta(n)$
$n$ $1024$ $|G|$ $2^{1024}$

Yuval Filmus
la source

Je vois votre point, mais cela ne pose-t-il pas un problème en P si nous choisissons la taille du groupe comme paramètre?

Nassim HADDAM du

Vous ne pouvez pas choisir le paramètre dans ce cas - le paramètre est toujours la longueur d'entrée.

Yuval Filmus

Merci pour les réponses. J'ai eu un problème avec ce qui pourrait arriver si nous considérons l'autre cas (problèmes de P devenant NP et inversement). Je peux voir clairement maintenant :).

Nassim HADDAM du

Nous ne faisons pas le calcul de façon unaire car notre objectif est de factoriser un certain nombre ou de calculer un logarithme discret, et peu nous importe comment le nombre est représenté. Le donner en entrée en binaire ou unaire n'affecte pas le "temps de mur" nécessaire pour résoudre le problème, seulement sa complexité en termes de taille d'entrée (puisque nous changeons la taille d'entrée!).

Yuval Filmus

De plus, nous ne pouvons pas vraiment avoir un entier long de 128 bits comme entrée unaire dans un algorithme du monde réel. Il n'y a pas assez d'atomes dans l'univers.

Yuval Filmus