Komplexität des Factorings in Zahlenfeldern

Was ist über die rechnerische Komplexität der Faktorisierung von ganzen Zahlen in allgemeinen Zahlenfeldern bekannt? Genauer:

1. Über die ganzen Zahlen stellen wir ganze Zahlen durch ihre binären Erweiterungen dar. Was ist die analoge Darstellung von ganzen Zahlen in allgemeinen Zahlenfeldern?
2. Ist bekannt, dass die Primalität über Zahlenfelder in P oder BPP liegt?
3. Was sind die bekanntesten Algorithmen zum Faktorisieren über Zahlenfelder? (Gehen die Algorithmen und von ?) Factoring bezieht sich hier auf die Darstellung einer Zahl (dargestellt durch Bits) als ein Produkt von Primzahlen.$\exp \sqrt n$$\exp n^{1/3}$$\mathbb{Z}$$n$
4. Wie komplex ist es, alle Faktorisierungen einer ganzen Zahl in einem Zahlenfeld zu finden? Um zu zählen, wie viele verschiedene Faktorisierungen es hat?
5. Über ist bekannt, dass es NP-schwer ist, zu entscheiden, ob eine gegebene Zahl einen Faktor in einem Intervall hat. Kann es sein, dass über den Ring von ganzen Zahlen in Zahlenfeldern herauszufinden, ob es einen Primfaktor gibt, dessen Norm in einem bestimmten Intervall liegt, bereits NP-schwer ist? $\mathbb{Z}$$[a,b]$
6. Berücksichtigt BQP Zahlenfelder?

Anmerkungen, Motivationen und Aktualisierungen.

Dabei ist natürlich entscheidend, dass die Faktorisierung über Zahlenfelder nicht eindeutig ist. Die Frage (insbesondere Teil 5) wurde durch diesen Blog-Beitrag über GLL (siehe diesen Hinweis ) und auch durch diese frühere TCSexchange-Frage motiviert. Ich präsentierte es auch über meinen Blog, wo Lior Silverman eine gründliche Antwort präsentierte .

Die folgende Antwort wurde ursprünglich als Kommentar in Gils Blog gepostet

(1) Sei ein Zahlenfeld , wobei angenommen wird, dass ein monisches Minimalpolynom . Man kann dann Elemente des Ringes von ganzen Zahlen als Polynome in oder auf integraler Basis darstellen - die beiden sind äquivalent.agr ; ) & agr ; f ≤ Z [ x ] O K$K=\mathbb{Q}(\alpha)$$\alpha$$f\in\mathbb{Z}[x]$$\mathcal{O}_K$$\alpha$

Wenn Sie nun wie in (1) korrigieren, gibt es eine Reduzierung der Polynomzeit vom Problem über zum Problem in . Um zu überprüfen, ob die Berechnungen (z. B. Schnittmenge eines Ideals mit oder Faktorisierung eines Polynoms ) in polynomieller Zeit durchgeführt werden können, siehe das Buch von Cohen, auf das in der vorherigen Antwort Bezug genommen wurde.K $K$$K$$\mathbb{Q}$$\mathbb{Z}$$p$

Als Vorberechnung für jede rationale Primzahl die die Diskriminante von ( dh die Diskriminante von ) dividiert , werden alle Primzahlen von die über .α f O K$p$$\alpha$$f$$\mathcal{O}_K$$p$

(2) Für primality Tests gegeben ideal lassen so sein , dass (dies kann in Polynomzeit berechnet werden und die Anzahl der Bits von ist in der Eingabe polynomiell). Überprüfen Sie in der Polynomzeit, ob eine Primzahl ist. Wenn nicht, dann ist keine Primzahl. Wenn ja, dann finden Sie die Primzahlen von die über entweder aus der Vorberechnung oder durch Faktorisierung von mod . Wenn eine Primzahl ist, muss es sich in jedem Fall um eine dieser Primzahlen handeln. p ∈ $\mathfrak{a}\triangleleft\mathcal{O}_K$$p\in\mathbb{Z}$ p p a O K p f p $\mathfrak{a}\cap\mathbb{Z} = p\mathbb{Z}$$p$$p$$\mathfrak{a}$$\mathcal{O}_K$$p$$f$$p$$\mathfrak{a}$

(3a), (6a) Für die Zerlegung in Primzahlen wird bei gegebenem idealen die Norm . Auch dies kann in der Polynomzeit gefunden werden und ist folglich nicht zu groß. Faktor in (entweder klassisch oder mit Shors Algorithmus, abhängig von der gewünschten Reduzierung). Dies gibt eine Liste von rationalen Primzahlen, die teilen , und daher können wir wie in 2 die Liste von Primzahlen von die teilen . Da Dies gibt die Liste der Primzahlen, die teilen. y = N K Q ( a ) = [ O K : a ] y Z y O K y a | y O K $\mathfrak{a}\triangleleft\mathcal{O}_K$$y = N^K_\mathbb{Q}(\mathfrak{a}) = [\mathcal{O}_K:\mathfrak{a}]$$y$$\mathbb{Z}$$y$$\mathcal{O}_K$$y$$\mathfrak{a} | y\mathcal{O}_K$$\mathfrak{a}$. Schließlich ist es einfach, den Exponenten zu bestimmen, in den eine Primzahl ein gegebenes Ideal teilt.

(3b), (6b) Aber Gil will die Faktorisierung nicht in Primzahlen, sondern in Irreduzible. Es stellt sich heraus, dass es bei gegebener Primfaktorisierung von möglich ist, eine Faktorisierung von effizient in irreduzible Elemente von zu konstruieren . Dazu sei die Klassennummer und man beachte, dass es möglich ist, die ideale Klasse eines gegebenen Ideals effizient zu berechnen. nun einen irreduziblen Teiler von wählen Sie Primideale (möglicherweise mit Wiederholung) aus der Faktorisierung von x O K h K x $x\mathcal{O}_K$$x$$\mathcal{O}_K$$h_K$$x$ x x h $h_K$$x$. Nach dem Pigeon-Hole-Prinzip multipliziert eine Teilmenge dieser Werte mit der Identität in der Klassengruppe. finde eine minimale solche Teilmenge. Sein Produkt ist dann ein Hauptideal, das durch ein nicht reduzierbares Element erzeugt wird. Teilen Sie durch dieses Element, entfernen Sie die relevanten Ideale aus der Faktorisierung und wiederholen Sie. Wenn die Faktorisierung weniger als Elemente enthält, nehmen Sie einfach eine minimale Teilmenge aller Faktoren.$x$$h_K$

(4) Ich denke, es ist möglich, die Faktorisierungen in irreduzible zu zählen, aber dies ist ein bisschen mehr Kombinatorik - bitte geben Sie mir Zeit, es auszuarbeiten. Andererseits ist es im Zusammenhang mit subexponentiellen Faktorisierungsalgorithmen nicht interessant, alle zu bestimmen, da es im Allgemeinen exponentiell viele solcher Faktorisierungen gibt.

(5) Ich habe keine Ahnung.

Wie von Daniel erwähnt, finden Sie einige Informationen in dem Buch A Course in Computational Algebraic Number Theory ( link ).

Insbesondere gibt es verschiedene Möglichkeiten, Elemente von Zahlenfeldern darzustellen. Let ein Nummernfeld sein mit einem Grad- monic irreduzible Polynom . Sei eine Wurzel von . Die sogenannte Standarddarstellung eines Elements ist das Tupel wobei , und , so dass& phiv; n Z [ ξ ] & thgr; & phiv; & agr; ∈ K ( a 0 , ... , a n - 1 , d ) a i ∈ Z d > 0 gcd ( a 0 , ... , a n - 1 , d ) = $K=Q[\xi]/\langle\varphi\rangle$$\varphi$$n$$\mathbb Z[\xi]$$\theta$$\varphi$$\alpha\in K$$(a_0,\dotsc,a_{n-1},d)$$a_i\in\mathbb Z$$d>0$$\gcd(a_0,\dotsc, a_{n-1},d)=1$