Integer Factoring über Gitterreduktion?

Ich fand einen Artikel mit dem Titel " Faktorisierung von ganzen Zahlen und Berechnung diskreter Logarithmen durch diophantinische Approximation " von CP Schnorr aus dem Jahr 1993. Es sieht so aus, als würde eine probabilistische Methode mit erwarteter Polynomlaufzeit (und Raum) vorgestellt, um eine ganzzahlige Faktorisierung durchzuführen.

Aus dem Artikel: "Ein Szenario zum Faktorisieren von ... Das entsprechende Gitterproblem ist für die derzeit bekannten Gitterreduktionsalgorithmen nicht durchführbar. Wir haben keine Erfahrung mit der Gitterbasisreduktion für Gitter mit der Dimension 6300. Die Bitlänge der Eingangsvektoren beträgt mindestens 1500. "$N \approx 2^{512}$

Ich verstehe dies so, dass der vorgestellte Algorithmus polynomisch ist, aber der Exponent und die Faktoren so groß sind, dass er für die aktuelle Technologie rechnerisch unpraktisch ist.

Kann jemand darüber nachdenken? Ist dieses Papier legitim? Ist das nicht eine große Neuigkeit, wenn es so ist? Bedeutet dies nicht, dass das Integer-Factoring in P wahrscheinlich ist? Haben die Leute Fortschritte gemacht, um Algorithmen zur Gitterreduzierung besser handhabbar zu machen?

$\gamma$

$\gamma$

Arora et al. ( PDF ) zeigen, dass die Approximation des nächsten Vektors innerhalb einer Konstanten NP-hart ist.

$\epsilon > 0$$2^{\log^{\frac{1}{2} - \epsilon}{n}}$

Dinur et al. ( ACM Citation ) verstärkten später das Ergebnis der Unannäherbarkeit auf:

$\epsilon > 0$$n^{\frac{\epsilon}{\log\log{n}}}$

Obwohl ich mit Schnorrs Arbeit nicht vertraut bin, würde mich das, was wir über Gitterprobleme wissen, zu der Annahme führen, dass dies nicht direkt zu einem Polynom-Zeit-Algorithmus führen soll. Schnorr verbringt viel Zeit damit, über tatsächliche Implementierungen zu sprechen (z. B. dauert das Ausführen dieses Programms auf einem solchen Computer ungefähr so ​​viele Wochen / Monate / Jahre / Äonen).

PS Wie Suresh betont, scheint es trotz der Komplexität eine Anstrengung zu sein, "schnell genug" oder "schnellere" Laufzeiten für die Ganzzahlfaktorisierung zu erhalten.

PPS Und wenn ich noch eine Vermutung anstellen kann: Angesichts der Tatsache, dass Schnorrs Arbeit die Arbeit an der Härte der Approximation von Gitterproblemen vorwegnimmt, besteht wahrscheinlich die ursprüngliche Hoffnung, dass dies zu einem Polynom-Zeit-Algorithmus für die ganzzahlige Faktorisierung geführt hat. In Anbetracht von Arora et al. Und Dinur et al. Ist jedoch klar, dass es auf diesem Weg keine Lösung (oder zumindest eine einfache Lösung) gibt.

Das Papier zeigt eine Reduktion vom Factoring auf ein Gitterproblem. Es wird nicht behauptet, dass das Gitterproblem in (probabilistischer) Polynomzeit gelöst werden kann. Ich verstehe, dass Schnorrs Behauptung stattdessen lautet, dass schnelle Implementierungen zum Auffinden kurzer Vektoren in Gittern (unabhängig untersucht, wie LLL usw.) dann für schnelle Implementierungen von Factoring-Lösungen verwendet werden können (ähnlich wie SAT-Löser häufig als schnelle verwendet werden können Unterprogramm zur Lösung anderer schwieriger Probleme)