Was ist die Worst-Case-Komplexität eines Zahlenfeldsiebs?

Gegeben Verbund allgemeinen Zahlkörpersieb ist am besten bekannt Faktorisierung Algorithmus für ganzzahlige Faktorisierung von . Es ist ein randomisierter Algorithmus und wir erhalten eine erwartete Komplexität von um zu faktorisieren . $N\in\Bbb N$ $N$ $O\Big(e^{\sqrt{\frac{64}{9}}(\log N)^{\frac 13}(\log\log N)^{\frac 23}}\Big)$ $N$

Ich habe nach Informationen zur Worst-Case-Komplexität dieses randomisierten Algorithmus gesucht. Ich kann jedoch keine Informationen finden.

(1) Was ist die Worst-Case-Komplexität eines Zahlenfeldsiebs?

(2) Kann hier auch die Zufälligkeit entfernt werden, um einen deterministischen subexponentiellen Algorithmus zu erhalten?

reference-request derandomization factoring average-case-complexity worst-case
quelle

Antworten:

Das Zahlenfeldsieb wurde noch nie gründlich analysiert. Die von Ihnen angegebene Komplexität ist lediglich heuristisch. Der einzige subexponentielle Algorithmus, der genau analysiert wurde, ist der Faktorisierungsalgorithmus von Dixon , der dem quadratischen Sieb sehr ähnlich ist. Laut Wikipedia läuft Dixons Algorithmus in der Zeit . Dixons Algorithmus ist randomisiert. $e^{O(2\sqrt{2}\sqrt{\log n\log\log n})}$

Alle (heuristisch) bekannten subexponentiellen Algorithmen erfordern eine Randomisierung. Dixons Algorithmus muss ganze Zahlen so finden, dass glatt (kann in ein Produkt kleiner Primzahlen einbezogen werden) und "zufällig" ist, und das Zahlenfeldsieb hat ähnliche, aber kompliziertere Anforderungen. Die elliptische Kurvenmethode muss eine elliptische Kurve modulo deren Ordnungsmodulo ein Faktor von glatt ist. In beiden Fällen scheint es schwierig zu sein, die Algorithmen zu derandomisieren. $x$ $x^2 \pmod{n}$ $n$ $n$

Die nominelle Worst-Case-Komplexität all dieser Algorithmen ist unendlich: Im Fall des quadratischen Siebs und des Zahlenfeldsiebs erzeugen Sie möglicherweise immer das gleiche , während Sie bei der elliptischen Kurvenmethode möglicherweise immer die gleiche elliptische Kurve erzeugen . Es gibt viele Möglichkeiten, dies zu umgehen, zum Beispiel einen exponentiellen Zeitalgorithmus parallel auszuführen. $x$

Yuval Filmus
quelle

Da Sie sich auch mit ECM befasst haben: Wir kennen einen subexp-randomisierten Algorithmus zur Berechnung von in mithilfe von ECM, wobei unbekannt und randomisiert ist. Haben Sie eine Schätzung, wie viele Versuche mit diesem Algorithmus ausreichen, um und wobei ?

n! r

$n!r$

O (e x p (\sqrt{\log n}))

$O(exp(\sqrt{\log n}))$

r

$r$

n! r

$n!r$

n! s

$n!s$

(r, s) = 1

$(r,s)=1$

Ich habe keine Ahnung, was ist, aber im Allgemeinen balancieren wir bei der Auswahl von Parametern in ECM zwischen der Wahrscheinlichkeit dass die Kurve glatt genug ist, und der Laufzeit die zum Testen jeder Kurve erforderlich ist. Normalerweise ist der Gleichgewichtspunkt ist , wenn . Die erwartete Anzahl von Versuchen sollte also .

n! r

$n!r$

p

$p$

T

$T$

1 / p \approx T

$1/p \approx T$

O (\exp \sqrt{\log n})

$O(\exp\sqrt{\log n})$

Yuval Filmus

n!

$n!$ ist Fakultät von . Es ist ein offenes Problem, die Komplexität der Fakultät auf eine gerade Linie zu bringen. Wir wissen, wie man berechnet, wobei in subexp-Zeit unbekannt ist. Wenn wir zwei verschiedene und , können wirin subexp Zeit wenn .

n

$n$

n! r

$n!r$

r

$r$

n! r

$n!r$

n! s

$n!s$

(n! r, n! s) = n!

$(n!r,n!s)=n!$

(r, s) = 1

$(r,s)=1$

Ich erinnere mich, vor einiger Zeit gerechnet zu haben. Ich glaube nicht, dass ich mich verbessern könnte, da es einen Haken gab und ich mich nicht an die Details erinnere.

Der letzte Absatz scheint seltsam und könnte genauer geklärt werden. Sprechen Sie von einem Szenario, in dem der RNG in dem Sinne "defekt" ist, dass er nicht den gesamten Verteilungsraum abtastet? aber dann würde da nicht parallelität helfen? wäre es denn das gleiche "kaputte" RNG parallel? oder ist die Idee, dass es sich um einen anderen RNG handelt, der parallel ausgeführt wird? Tatsächlich ist die parallele Komplexität von Factoring-Algorithmen ein ganz anderes komplexes Thema, z. B. können einige besser parallelisiert werden als andere, Big-O ist möglicherweise nicht genau anwendbar usw.

vzn

In den letzten Monaten wurde eine Version des Zahlenfeldsiebs streng analysiert: http://www.fields.utoronto.ca/talks/rigorous-analysis-randomized-number-field-sieve-factoring

Grundsätzlich ist die Worst-Case-Laufzeit unbedingt und unter GRH. Dies gilt nicht für das "klassische" Zahlenfeldsieb, sondern für eine leicht modifizierte Version, bei der mehr Schritte zufällig angeordnet werden, um die Komplexitätsanalyse zu vereinfachen. $L_n(1/3, 2.77)$ $L_n(1/3, (64/9)^{1/3})$

Ich glaube, das entsprechende Papier wird noch geprüft.

Update: Das Papier ist jetzt raus. Jonathan D. Lee und Ramarathnam Venkatesan, "Rigorose Analyse eines randomisierten Zahlenfeldsiebs", Journal of Number Theory 187 (2018), S. 92-159, doi: 10.1016 / j.jnt.2017.10.019

djao
quelle

Können Sie eine vollständigere Referenz mit Titel, Autor und Veröffentlichungsort angeben, damit die Antwort auch dann noch nützlich ist, wenn der Link nicht mehr funktioniert?

Da das Ergebnis erst vor kurzem bekannt gegeben wurde, wird es meines Erachtens derzeit geprüft, wie in meiner Antwort angegeben, und daher noch nicht veröffentlicht. Ich werde meine Antwort in Zukunft aktualisieren, sobald Veröffentlichungsinformationen verfügbar sind.

Djao

FWIW scheint es nicht auf arxiv.org zu geben. Der Autor ist jedoch Ramarathnam Venkatesan, der möglicherweise bei zukünftigen Suchanfragen hilfreich ist, falls diese erforderlich sein sollten.

Peter Taylor

Es ist eigentlich ein Zwei-Autoren-Werk (JD Lee und R. Venkatesan): cmi.ac.in/activities/…

Sary