In der Arbeit von Adi Shamir [1] aus dem Jahr 1979 zeigt er, dass Factoring in einer polynomiellen Anzahl von arithmetischen Schritten durchgeführt werden kann . Diese Tatsache wurde in der jüngsten Veröffentlichung von Borwein und Hobart [2] im Zusammenhang mit linearen Programmen (SLP) wiederholt und ist mir daher aufgefallen.
Da ich ziemlich überrascht war, dies zu lesen, habe ich die folgende Frage: Gibt es andere kryptografische Probleme oder vielleicht auch andere relevante Probleme, die in einer polynomiellen Anzahl von Schritten mit einem SLP gelöst werden können und von denen derzeit nicht bekannt ist, dass sie lösbar sind effizient auf einem "normalen" klassischen Computer?
[1] Adi Shamir, Faktorisierung von Zahlen in arithmetischen Schritten . Information Processing Letters 8 (1979) S. 28–31
[2] Peter Borwein, Joe Hobart, Die außergewöhnliche Teilungskraft in geraden Programmen , The American Mathematical Monthly Vol. 7 (August bis September 2012), S. 584-592
Antworten:
Ich habe das Papier auch nicht gelesen, aber die Zusammenfassung scheint zu sagen, dass eine exponentielle Anzahl von Bitoperationen erforderlich ist.
Chebyshevs Arbeit über Kongruenzen und seine Neuformulierung im AKS-Algorithmus zeigen, dass die Primgenerierung in P liegt. Daher liefert die Teilung von Versuchen nicht triviale Faktoren. In diesem Fall können Sie für einige Zahlen N eine Dichte von Primzahlen von 1 / ln (N) erwarten.
Darüber hinaus können Sie sich Turings Doktorarbeit von 1937 zu diesem Thema ansehen.
quelle