Złożoność faktoringu w polach liczbowych

Co wiadomo na temat złożoności obliczeniowej liczb całkowitych faktoringu w ogólnych polach liczbowych? Dokładniej:

1. Nad liczbami całkowitymi reprezentujemy liczby całkowite poprzez ich binarne rozszerzenia. Jakie są analogiczne reprezentacje liczb całkowitych w ogólnych polach liczbowych?
2. Czy wiadomo, że pierwszeństwo nad polami liczbowymi ma postać P lub BPP?
3. Jakie są najbardziej znane algorytmy faktorowania w polach liczbowych? (Wykonaj $\exp \sqrt n$ i (pozornie)$\exp n^{1/3}$ algorytmy rozciągają się od$\mathbb{Z}$?) Tutaj, faktoring odnosi się do znalezienia pewną reprezentację liczby (reprezentowany przez$n$bitów) jako produkt liczb pierwszych.
4. Jaka jest złożoność znalezienia wszystkich faktoryzacji liczby całkowitej w polu liczbowym? Policzenia, ile ma różnych faktoryzacji?
5. Ponad $\mathbb{Z}$ wiadomo, że przy podejmowaniu decyzji, czy dana liczba ma czynnik w przedziale $[a,b]$ jest trudne dla NP. Czy poza pierścieniem liczb całkowitych w polach liczbowych może się zdarzyć, że ustalenie, czy istnieje czynnik główny, którego norma jest w określonym przedziale, jest już trudne NP?
6. Czy faktoring w polach liczbowych w BQP?

Uwagi, motywacje i aktualizacje.

Oczywiście kluczowy jest tutaj fakt, że faktoryzacja nie jest unikalna dla pól liczbowych. Pytanie (szczególnie część 5) było motywowane tym postem na blogu nad GLL (patrz ta uwaga ), a także wcześniejszym pytaniem TCSexchange. Przedstawiłem to również na moim blogu, na którym Lior Silverman przedstawił dokładną odpowiedź .

Poniższa odpowiedź została pierwotnie opublikowana jako komentarz na blogu Gila

(1) Niech będzie polem liczbowym, w którym zakładamy, że α ma monomiczny minimalny wielomian f ∈ Z [ x ] . Następnie można reprezentować elementy pierścienia liczb całkowitych O K jako wielomianów w α lub w kategoriach integralnej podstawy - oba są równoważne.$K=\mathbb{Q}(\alpha)$$\alpha$$f\in\mathbb{Z}[x]$$\mathcal{O}_K$$\alpha$

Teraz mocowania jak w (1) jest wielomianem zmniejszenie czasu problem polegający na K problemu w Q . Aby sprawdzić, czy obliczenia (np. Przecięcie ideału z Z lub faktoring modu wielomianowego p ) można wykonać w czasie wielomianowym, zobacz książkę Cohena, o której mowa w poprzedniej odpowiedzi.$K$$K$$\mathbb{Q}$$\mathbb{Z}$$p$

Jako wstępne obliczenie dla każdej racjonalnej liczby pierwszej dzielącej dyskryminator α (czyli dyskryminatora f ) znajdź wszystkie liczby pierwsze O K leżące powyżej p .$p$$\alpha$$f$$\mathcal{O}_K$$p$

(2) W przypadku testowania pierwotności, dla idealnej niech p ∈ Z będzie takie, że a ∩ Z = p Z (można to obliczyć w czasie wielomianowym, a liczba bitów p jest wielomianowa na wejściu). Sprawdź w czasie wielomianowym, czy p jest liczbą pierwszą. Jeśli nie, to a nie jest liczbą pierwszą. Jeśli tak, to znajdź liczby pierwsze O K leżące powyżej p albo na podstawie wstępnego obliczenia, albo przez uwzględnienie f mod p . W każdym razie, jeśli a jest liczbą pierwszą, musi być jedną z tych liczb pierwszych.$\mathfrak{a}\triangleleft\mathcal{O}_K$$p\in\mathbb{Z}$$\mathfrak{a}\cap\mathbb{Z} = p\mathbb{Z}$$p$$p$$\mathfrak{a}$$\mathcal{O}_K$$p$$f$$p$$\mathfrak{a}$

(3a), (6a) Dla faktoryzacji w liczbach pierwszych, dla idealnego znajdź jego normę y = N K Q ( a ) = [ O K : a ] . Znów można to znaleźć w czasie wielomianowym, a zatem nie jest zbyt duże. Współczynnik y w Z (klasycznie lub przy użyciu algorytmu Shora, w zależności od żądanej redukcji). Daje to listę racjonalnych liczb pierwszych dzielących y , a zatem, podobnie jak w 2, możemy znaleźć listę liczb pierwszych O K dzielących y . Od | $\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$ daje to listę liczb pierwszych dzielących a . Wreszcie łatwo jest wyznaczyć wykładnik, do którego liczba pierwsza dzieli dany ideał.$\mathfrak{a} | y\mathcal{O}_K$$\mathfrak{a}$

(3b), (6b) Ale Gil chce faktoryzacji w nieredukowalne, a nie w liczbach pierwszych. Okazuje się, że ze względu na czynniki pierwsze można budować efektywnie jeden faktoryzacji X w nieredukowalnych elementów O K . W tym celu niech h K będzie numerem klasy i zwróć uwagę, że można skutecznie obliczyć idealną klasę danego ideału. Teraz, aby znaleźć nieredukowalny dzielnik x, wybierz h podstawowe ideały K (ewentualnie z powtórzeniem) z faktoryzacji $x\mathcal{O}_K$$x$$\mathcal{O}_K$$h_K$$x$$h_K$$x$. Zgodnie z zasadą szufladki pewien podzbiór tych mnoży się do tożsamości w grupie klasowej; znajdź minimalny taki podzbiór. Jego produkt jest wówczas głównym ideałem generowanym przez element nieredukowalny. Podziel przez ten element, usuń odpowiednie ideały z faktoryzacji i powtórz. Jeśli rozkład na czynniki ma mniej niż h K elementów, wystarczy wziąć minimalny podzbiór wszystkich czynników.$x$$h_K$

(4) Myślę, że można policzyć faktoryzacje na nieredukowalne, ale jest to trochę dodatkowa kombinatoryka - proszę dać mi czas na wypracowanie tego. Z drugiej strony ustalenie ich wszystkich nie jest interesujące w kontekście algorytmów faktoryzacji sub wykładniczej, ponieważ generalnie istnieje wiele wykładniczo takich faktoryzacji.

(5) Nie mam pojęcia.

Jak wspomniał Daniel, niektóre informacje można znaleźć w książce A Course in Computational Algebraic Number Theory ( link ).

W szczególności istnieje kilka sposobów przedstawiania elementów pól liczbowych. Niech być Pole numeru z φ stopnio n monic nieredukowalnego wielomianu Z [ ξ ] . Niech θ będzie dowolnym źródłem φ . Tak zwana standardowa reprezentacja elementu α ∈ K jest krotką ( 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)$gdzie , d > 0 i gcd ( a 0 , … , a n - 1 , d ) = 1 , tak że α = $a_i\in\mathbb Z$$d>0$$\gcd(a_0,\dotsc, a_{n-1},d)=1$