Complejidad de factoring en campos numéricos

25

¿Qué se sabe sobre la complejidad computacional de factorizar enteros en campos de números generales? Más específicamente:

  1. Sobre los enteros representamos enteros a través de sus expansiones binarias. ¿Cuáles son las representaciones análogas de enteros en los campos numéricos generales?
  2. ¿Se sabe que la primalidad sobre los campos numéricos está en P o BPP?
  3. ¿Cuáles son los algoritmos más conocidos para factorizar sobre campos numéricos? (Haz la expnorte y el (aparentemente)expn1/3 algoritmos se extienden desdeZ?) Aquí, la factorización se refiere a la búsqueda de alguna representación de un número (representado pornortebits) como un producto de números primos.
  4. ¿Cuál es la complejidad de encontrar todas las factorizaciones de un número entero en un campo numérico? ¿De contar cuántas factorizaciones distintas tiene?
  5. Sobre Z se sabe que decidir si un número dado tiene un factor en un intervalo [a,b] es NP-difícil. Sobre el anillo de números enteros en los campos numéricos, ¿puede ser el caso que encontrar si hay un factor primo cuya norma está en un cierto intervalo ya es NP-duro?
  6. ¿Está factorizando en campos de números en BQP?

Observaciones, motivaciones y actualizaciones.

Por supuesto, el hecho de que la factorización no es única en los campos numéricos es crucial aquí. La pregunta (especialmente la parte 5) fue motivada por esta publicación de blog sobre GLL (ver este comentario ), y también por esta pregunta anterior de TCSexchange. Lo presenté también en mi blog donde Lior Silverman presentó una respuesta exhaustiva .

Gil Kalai
fuente
¿Puede dar un ejemplo? ¿en qué se diferencia la factorización en campos defn de la factorización entera recta?
vzn
2
Para (0): supongo que por lo general un campo de número se representa como Q [ ξ ] /φ donde φ es un polinomio irreducible. Entonces, un elemento de K es una tupla de pares ( ( n 0 , d 0 ) , ( n 1 , d 1 ) , , ( n δ - 1 , d δ - 1 ) ) donde δ = degKQ[ξ]/φφK((n0,d0),(n1,d1),,(nδ1,dδ1)) . Esto significa que su elemento es n 0 / d 0 + n 1 ξ / d 1 + + n δ - 1 ξ δ - 1 / d δ - 1 . δ=deg(φ)n0/d0+n1ξ/d1++nδ1ξδ1/dδ1
Bruno
2
@ Gil ¿Has visto este libro antes? springer.com/mathematics/numbers/book/978-3-540-55640-4 No tengo acceso a mi copia en este momento (aunque lo haré nuevamente en unos días, y lo comprobaré). Me gustaría ver si hay algo escrito sobre la factorización en (i) campos de números algebraicos, o (ii) dominios Dedekind, con número de clase> 1.
Daniel Apon
44
@vzn: Sin poner palabras en la boca de Gil, estoy bastante seguro de que se refiere a extensiones finitas de los racionales (exactamente a lo que se vinculó). Cuando dice "factorizando en un campo así", estoy bastante seguro de que quiere decir factorizar en el anillo de enteros de dicho campo. La misma página de wikipedia a la que se vinculó tiene una sección en el anillo de enteros en un campo de número algebraico.
Joshua Grochow
1
@vzn El tamiz de campo numérico usa campos numéricos para factorizar enteros.
Yuval Filmus

Respuestas:

14

La siguiente respuesta se publicó originalmente como un comentario en el blog de Gil

(1) Sea un campo numérico, donde suponemos que α tiene un polinomio mínimo monico f Z [ x ] . Entonces se pueden representar elementos del anillo de enteros O K como polinomios en α o en términos de una base integral; los dos son equivalentes.K=Q(α)αFZ[X]OKα

Ahora la fijación de como en (1) hay una reducción de tiempo polinómico del problema sobre K al problema en Q . Para verificar que los cálculos (por ejemplo, la intersección de un ideal con Z o la factorización de un mod polinomial p ) se pueden realizar en tiempo polinómico, consulte el libro de Cohen mencionado en la respuesta anterior.KKQZpags

Como precomputación para cada primo racional dividiendo el discriminante de α (que es el discriminante de f ), encuentre todos los primos de O K que se encuentran por encima de p .pagsαFOKpags

(2) Para la prueba de primalidad, dado un ideal dejó p Z sea tal que unZ = p Z (esto se puede calcular en tiempo polinómico y el número de bits de p es polinomio en la entrada). Verifique en tiempo polinómico si p es primo. Si no, entonces a no es primo. En caso afirmativo, encuentre los primos de O K que se encuentran por encima de p, ya sea desde la precomputación o factorizando f mod p . En cualquier caso, si a es primo, debe ser uno de esos primos.unaOKpagsZunaZ=pagsZpagspagsunaOKpagsFpa

(3a), (6a) Para factorizar en números primos, dado un ideal encuentre su norma y = N K Q ( a ) = [ O K : a ] . De nuevo, esto se puede encontrar en el tiempo polinómico y, en consecuencia, no es demasiado grande. Factorice y en Z (ya sea clásicamente o usando el algoritmo de Shor, dependiendo de la reducción que desee). Esto proporciona una lista de primos racionales que dividen y , y por lo tanto, como en 2, podemos encontrar la lista de primos de O K que dividen y . Desde un | yaOKy=NQK(a)=[OK:a]yZyOKy esto da la lista de números primos que dividen a . Finalmente, es fácil determinar el exponente al que un primo divide un ideal dado.a|yOKa

(3b), (6b) Pero Gil quiere la factorización en irreducibles, no en números primos. Resulta que, dada la factorización prima de es posible construir de manera eficiente una factorización de x en elementos irreducibles de O K . Por esta let h K es el número de clases, y la nota que es posible calcular de manera eficiente el ideal de la clase de un ideal dado. Ahora, para encontrar un divisor irreducible de x, seleccione h K ideales ideales (posiblemente con repetición) a partir de la factorización de xxOKxOKhKxhKx. Por el principio del casillero, algunos subconjuntos de esos se multiplican a la identidad en el grupo de clase; encuentra un mínimo de ese subconjunto. Su producto es entonces un ideal principal generado por un elemento irreducible. Divida por este elemento, elimine los ideales relevantes de la factorización y repita. Si la factorización tiene menos de h elementos K , simplemente tome un subconjunto mínimo de todos los factores.xhK

(4) Creo que es posible contar las factorizaciones en irreducibles, pero esto es un poco de combinatoria adicional; por favor, deme tiempo para resolverlo. Por otro lado, determinarlos a todos no es interesante en el contexto de los algoritmos de factorización sub-exponencial ya que en general hay exponencialmente muchas de esas factorizaciones.

(5) No tengo idea.

Lior Silberman
fuente
5

Como mencionó Daniel, puede encontrar algunas informaciones en el libro A Course in Computational Algebraic Number Theory ( enlace ).

En particular, hay varias formas de representar elementos de campos numéricos. Let ser un campo de número con φ un grado- n polinomio irreducible mónico de Z [ ξ ] . Deje θ ser cualquier raíz de φ . La llamada representación estándar de un elemento α K es la tupla ( a 0 , ... , a n - 1 , d )K=Q[ξ]/φφnZ[ξ]θφαK(a0,,an1,d)donde , d > 0 y mcd ( a 0 , , a n - 1 , d ) = 1 , de modo que α = 1aiZd>0gcd(a0,,an1,d)=1

α=1di=0n1aiθi.
Bruno
fuente