Complexidade de fatoração em campos numéricos

25

O que se sabe sobre a complexidade computacional de fatorar números inteiros em campos numéricos gerais? Mais especificamente:

  1. Sobre os números inteiros, representamos números inteiros por meio de suas expansões binárias. Quais são as representações análogas de números inteiros nos campos numéricos gerais?
  2. É sabido que a primalidade sobre os campos numéricos está em P ou BPP?
  3. Quais são os algoritmos mais conhecidos para fatorar sobre campos numéricos? (Faça o expn a (aparentemente) eexpn1/3 algoritmos estendem-se desdeZ?) Aqui, factoring refere-se encontrar alguns representação de um número (representado pornbits) como um produto de números primos.
  4. Qual é a complexidade de encontrar todas as fatorações de um número inteiro em um campo numérico? De contar quantas fatorações distintas ele possui?
  5. Sobre Z , sabe-se que decidir se um determinado número tem um fator em um intervalo [a,b] é NP-difícil. Sobre o anel de números inteiros nos campos numéricos, pode ser o caso de descobrir se existe um fator primordial cuja norma está em um determinado intervalo já é difícil para NP?
  6. O fatoramento está em campos numéricos no BQP?

Observações, motivações e atualizações.

É claro que o fato de a fatoração não ser exclusiva sobre os campos numéricos é crucial aqui. A questão (especialmente a parte 5) foi motivada por esta postagem no blog sobre a GLL (veja esta observação ) e também por essa pergunta anterior do TCSexchange. Apresentei também no meu blog, onde Lior Silverman apresentou uma resposta completa .

Gil Kalai
fonte
Você pode dar um exemplo? como o fatoramento nos campos define diferente do fatoramento inteiro direto?
vzn
2
Para (0): acho geralmente um campo de número de está representada como Q [ ξ ] /φ onde φ é um polinómio irredutível. Então, um elemento de K é uma tupla de pares ( ( n 0 , d 0 ) , ( n 1 , d 1 ) , , ( n δ - 1 , d δ - 1 ) ) onde δ = degKQ[ξ]/φφK((n0,d0),(n1,d1),,(nδ1,dδ1)) . Isso significa que seu elemento é n 0 / d 0 + n 1 ξ / d 1 + + n δ - 1 ξ δ - 1 / d δ - 1 . δ=deg(φ)n0/d0+n1ξ/d1++nδ1ξδ1/dδ1
de Bruno
2
@ Gil Você já viu este livro antes? springer.com/mathematics/numbers/book/978-3-540-55640-4 Não tenho acesso à minha cópia no momento (embora eu tenha novamente em alguns dias e verificarei isso). Gostaria de ver se há algo escrito sobre fatoração em (i) campos numéricos algébricos ou (ii) domínios Dedekind, com número de classe> 1. #
Daniel Daniel Apon
4
@vzn: Sem colocar palavras na boca de Gil, tenho certeza de que ele quer dizer extensões finitas dos racionais (exatamente a que você se vinculou). Quando ele diz "fatorando em tal campo", tenho quase certeza de que ele significa fatorar no anel de números inteiros de tal campo. A mesma página da wikipedia à qual você vinculou possui uma seção no anel de números inteiros em um campo de número algébrico.
Joshua Grochow
1
@vzn A peneira de campo numérico usa campos numéricos para fatorar números inteiros.
Yuval Filmus

Respostas:

14

A resposta a seguir foi postada originalmente como um comentário no blog de Gil

(1) Seja um campo numérico, onde assumimos que α possui um polinômio mínimo monônico f Z [ x ] . Pode-se então representar elementos do anel de números inteiros O K como polinómios em α ou em termos de uma base integrante - os dois são equivalentes.K=Q(α)αfZ[x]OKα

Agora fixação como em (1) há uma redução em tempo polinomial do problema ao longo do K para o problema em Q . Verificar se os cálculos (por exemplo, cruzando um ideal com Z ou fatorando um mod polinomial pKKQZp ) podem ser feitos em tempo polinomial, consulte o livro de Cohen mencionado na resposta anterior.

Como precomputation para cada imunização racional dividindo o discriminante de α (que é o discriminante F ) encontrar todos os números primos de O K encontra-se acima de p .pαfOKp

(2) Para o ensaio primality, dado um ideal deixar p Z ser tal que umaZ = P Z (isto pode ser calculado em tempo polinomial e o número de bits de p é polinomial na entrada). Verifique no tempo polinomial se p é primo. Caso contrário, a não é primo. Se sim, então encontrar os primos de O K deitado acima p a partir do precomputation ou por factoring f mod p . De qualquer forma, se umaOKpZaZ=pZppaOKpfpa é primo, deve ser um desses primos.

(3a), (6a) Para fatorar em primos, dado um ideal encontre sua norma y = N K Q ( a ) = [ O K : a ] . Novamente, isso pode ser encontrado no tempo polinomial e, consequentemente, não é muito grande. Fator y em Z (classicamente ou usando o algoritmo de Shor, dependendo da redução desejada). Isto dá uma lista de números primos racionais divisão y , e, portanto, como em 2 podemos encontrar a lista de números primos de O K dividindo y . Desde a | yaOKy=NQK(a)=[OK:a]yZyOKy isso dá a lista de números primos que dividem um . Finalmente, é fácil determinar o expoente ao qual um primo divide um dado ideal.a|yOKa

(3b), (6b) Mas Gil quer a fatoração em irredutíveis, não em primos. Acontece que, dada a fatoração principal de é possível construir de forma eficiente uma fatoração de x em elementos irredutíveis de O K . Para isso vamos h K ser o número da classe, e nota que é possível calcular de forma eficiente a classe ideal de um determinado ideal. Agora, para encontrar um divisor irredutível de x, selecione h K ideais ideais (possivelmente com repetição) a partir da fatoração dexOKxOKhKxhKx. Pelo princípio do buraco do pombo, algum subconjunto desses se multiplica à identidade no grupo de classes; encontre um subconjunto mínimo. Seu produto é então o principal ideal gerado por um elemento irredutível. Divida por esse elemento, remova os ideais relevantes da fatoração e repita. Se a fatoração tiver menos de h KxhK elementos , basta pegar um subconjunto mínimo de todos os fatores.

(4) Eu acho que é possível contar as fatorações em irredutíveis, mas isso é um pouco de combinatória extra - por favor, me dê tempo para resolver isso. Por outro lado, determinar todos eles não é interessante no contexto de algoritmos de fatoração subexponencial, uma vez que, em geral, existem exponencialmente muitas dessas fatorações.

(5) não faço ideia.

Lior Silberman
fonte
5

Como mencionado por Daniel, você pode encontrar algumas informações no livro Um Curso em Teoria dos Números Algébricos Computacionais ( link ).

Em particular, existem várias maneiras de representar elementos de campos numéricos. Let ser um campo de número com φ um degree- n polinomial irredutível mônico de Z [ ξ ] . Seja θ qualquer raiz de φ . A chamada representação padrão de um elemento α K é a tupla ( a 0 , , a n - 1 , dK=Q[ξ]/φφnZ[ξ]θφαK(a0,,an1,d)onde , d > 0 e gcd ( a 0 , , a n - 1 , d ) = 1 , de modo que α = 1aiZd>0gcd(a0,,an1,d)=1

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