Problèmes (cryptographiques) pouvant être résolus dans un nombre polynomial d'étapes arithmétiques

9

Dans l'article d'Adi Shamir [1] de 1979, il montre que l'affacturage peut se faire en un nombre polynomial d' étapes arithmétiques . Ce fait a été réaffirmé et a donc été porté à mon attention dans le récent article de Borwein et Hobart [2] dans le contexte des programmes en ligne droite (SLP).

Puisque j'ai été plutôt surpris de lire ceci, j'ai la question suivante: y a-t-il d'autres problèmes cryptographiques ou peut-être aussi d'autres problèmes pertinents, qui peuvent être résolus en un nombre polynomial d'étapes avec un SLP et qui ne sont actuellement pas connus pour être résolus efficacement sur un ordinateur classique "normal"?

[1] Adi Shamir, Factoring Numbers in step arithmeticO(log⁡n) . Lettres de traitement de l'information 8 (1979) S. 28–31

[2] Peter Borwein, Joe Hobart, The Extraordinary Power of Division in Straight Line Programs , The American Mathematical Monthly Vol. 119, n ° 7 (août ‒ septembre 2012), pp. 584-592

cc.complexity-theory cr.crypto-security algebraic-complexity Etsch
la source
Que signifie «résoluble en nombre polynomial d'étapes arithmétiques»? Les meilleurs algorithmes de factorisation actuellement disponibles prennent du temps sous-exponentiel (mais super-polynomial). Je ne trouve nulle part le journal de Shamir.
mikeazo
Je suggère de publier ceci sur Crypto.SE car vous n'avez pas obtenu beaucoup de réponses ici.
mikeazo
Il y a une entrée de blog connexe par Lipton: rjlipton.wordpress.com/2012/10/16/… Ce modèle de calcul est une sorte de tricherie, car vous autorisez les calculs avec une précision arbitraire et longue. Je ne suis pas au courant d'autres problèmes liés à la cryptographie qui ont été résolus dans ce modèle. Mais le modèle est si puissant qu'il pourrait valoir la peine d'être essayé.
minar
@minar le problème de triche n'est pas avec une précision aribtraire. la tricherie est ici avec des opérations de plancher et de plafond.
T ....

Réponses:

-2

Je n'ai pas lu le document aussi mais l'abrégé semble dire qu'un nombre exponentiel d'opérations sur les bits est requis.

Les travaux de Chebyshev sur les congruences et sa reformulation dans l'algorithme AKS montrent que la génération principale est en P. Par conséquent, la division d'essai donne des facteurs non triviaux. Dans ce cas, pour un certain nombre N, vous pouvez vous attendre à une densité de nombres premiers de 1 / ln (N).

En outre, vous pouvez consulter la thèse de doctorat de Turing de 1937 sur le sujet.

Phil
la source
3
Salut Phil. Bienvenue sur cstheory. Vous avez publié des réponses à de nombreuses questions en peu de temps, ce qui n'est pas habituel ici. Les messages qui sont vraiment des commentaires et non des réponses à la question ne doivent pas être publiés comme réponses. Vous voudrez peut-être regarder autour de vous et vérifier d'autres questions et comment les choses fonctionnent ici avant de poster plus de réponses.
Kaveh