Das Addieren von ganzen Zahlen, die durch ihre Faktorisierung dargestellt werden, ist genauso schwierig wie das Faktorisieren? Referenzanfrage

Ich suche eine Referenz für das folgende Ergebnis:

Das Hinzufügen von zwei Ganzzahlen in der faktorisierten Darstellung ist so schwierig wie das Faktorieren von zwei Ganzzahlen in der üblichen binären Darstellung.

(Ich bin mir ziemlich sicher, dass es da draußen ist, weil ich mich das irgendwann gefragt hatte und dann aufgeregt war, als ich es endlich in gedruckter Form sah.)

"Addieren von zwei Ganzzahlen in die faktorisierte Darstellung" ist das Problem: Ausgehend von den Primfaktoren zweier Zahlen und wird die Primfaktorisierung von ausgegeben . Beachten Sie, dass der naive Algorithmus für dieses Problem die Faktorisierung in der binären Standarddarstellung als Unterroutine verwendet.y x + $x$$y$$x+y$

Update : Danke Kaveh und Sadeq für die Beweise. Je mehr Beweise, desto besser, aber ich möchte auch dazu ermutigen, mehr Hilfe bei der Suche nach einer Referenz zu leisten, von der ich , wie gesagt, ziemlich sicher bin, dass sie existiert. Ich erinnere mich, es in einem Artikel gelesen zu haben, der andere interessante und nicht oft diskutierte Ideen enthielt, aber ich erinnere mich nicht, was diese anderen Ideen waren oder worum es in dem Artikel im Allgemeinen ging.

Angenommen, wir können das Problem in der Komplexitätsklasse lösen (nennen wir es FactSum), und ist unter -iteration (aka -bounded recursion) geschlossen (z. B. wenn wir berechnen können, wobei eine binäre Funktion ist, wir können berechnen und enthalten (diese letzte Bedingung kann schwächer gemacht werden). Wir zeigen, dass Factoring auch in .C log log x ∗ y ∗ x 1 ∗ … ∗ x log n P$C$$C$$\log$$\log$$x*y$$*$$x_1*\ldots*x_{\log{n}}$$\mathsf{P}$$C$

Beachten Sie, dass jede Zahl als Summe von geschrieben werden Potenzen von . Jeder von ihnen ist leicht zu faktorisieren.$\log n$$2$

Geben Sie nun eine Zahl ein, schreiben Sie sie als die Summe ihrer Potenzen, schreiben Sie dann jeden Summanden in die Faktorisierungsdarstellung und verwenden Sie dann den Algorithmus, um sie in der Faktorisierungsdarstellung zu summieren. Das Ergebnis ist das Faktorisieren der eingegebenen Nummer.

Dies zeigt, dass Factoring auf die Ihres Problems FactSum reduziert werden kann. Daher ist Factoring in (und ich denke, dass hier durch werden kann).P FactSum P N C $\log$$\mathsf{P}^{\text{FactSum}}$$\mathsf{P}$$\mathsf{NC^1}$

Mir ist kein Hinweis bekannt, aber ich glaube, ich habe einen Beweis gefunden:

Angenommen, Sie haben ein Orakel , bei dessen Eingabe zwei faktorisierte Zahlen eingegeben werden$\mathcal{O}$

$x = \prod_{i=1}^n p_i^{\alpha_i}$

und

$y = \prod_{i=1}^m q_i^{\beta_i} \enspace$,

gibt die Faktorisierung von .$x+y$

Wenn wir Zugriff auf , können wir mit der folgenden rekursiven Prozedur eine beliebige Zahl N in der Polynomzeit faktorisieren.$\mathcal{O}$$N$

VERFAHREN Faktor ( )$N$

1. Finden Sie eine prime , so daß N / 2 ≤ x ≤ N - 1 , und sei y = N - x .$x$$N/2 \le x \le N-1$$y = N - x$
2. Wenn keine Primzahl ist, erhalten Sie die Faktorisierung von y durch den rekursiven Aufruffaktor ( y ) und geben Sie O ( x , f a c t o r ( y ) ) aus .$y$$y$$y$$\mathcal{O}(x, factor(y))$
3. Andernfalls wird ausgegeben .$\mathcal{O}(x,y)$

Analyse:

Nach dem Primzahlsatz für groß genug gibt es viele Primzahlen zwischen N / 2 und N - 1 . Wenn N so klein ist, dass keine Primzahl in dieses Intervall fällt, können Sie N leicht faktorisieren. Daher ist Schritt 1 erfolgreich.$N$$N/2$$N-1$$N$$N$

In Schritt 2 können Sie AKS oder einen beliebigen anderen Polynomial-Time-Primality-Test verwenden.

Die Anzahl der Rekursionen ist einfach , da bei jedem Schritt N (mindestens) halbiert wird.$O(\lg(N)) = O(|N|)$$N$

PS-1: Angenommen, Goldbachs Vermutung könnte helfen, das Verfahren für gerade (und möglicherweise ungerade) ganze Zahlen zu beschleunigen.

PS-2: Die verwendete Reduktion ist eine Cook-Reduktion. Man könnte daran interessiert sein, den Beweis mit Karp-Reduktionen durchzuführen.

Diese Antwort ist unabhängig von meiner vorherigen Antwort . Ziel ist es, @ Kavehs Anliegen in den Kommentaren anzusprechen:

Es ist einfach zu tun , wenn wir wollten Zahlen, aber ich sehe nicht , wie es zu tun , auch mit log log n Zahlen.$\log n$$\log \log n$

Ich hatte ähnliche Bedenken:

Die verwendete Reduktion ist eine Cook-Reduktion. Man könnte daran interessiert sein, den Beweis mit Karp-Reduktionen durchzuführen.

(Karp-Kürzungen sind für Entscheidungsprobleme. Mit Karp-Kürzungen meine ich hier eine Cook-Kürzung mit nur einer Abfrage. Entschuldigung für nicht standardmäßige Terminologie!)

Die Antwort unten basiert auf den Diskussionen hier: /math/54580/factoring-some-integer-in-the-given-interval .

In dieser Antwort werde ich eine deterministische Karp-Reduktion in Polynimialzeit vom Faktorisieren zum Faktorisieren der Summe von zwei durch ihre Faktorisierungen dargestellten ganzen Zahlen angeben . Es gibt jedoch einen Haken: Im Verlauf des Beweises werde ich die folgende zahlentheoretische Annahme verwenden:

$p_n$$p_{n+1}$$p_{n+1} - p_n = O(\log^2p_n)$

$N$$n=|N|=O(\log N)$$N$$[N - \log^3N, N]$$\log^3N = O(n^3)$

$x$$[N - \log^3N, N]$$y=N-x$

$0 \le y \le \log^3N$$|y| = O(\log \log N) = O(\log n)$$y$

$(x,y)$$N = x+y$