Qual é a pior complexidade da peneira de campo numérico?

Dado composto peneira campo número geral é melhor conhecido algoritmo fatoração para fatoração número inteiro de . É um algoritmo aleatório e obtemos uma complexidade esperada de para fator . $N\in\Bbb N$ $N$ $O\Big(e^{\sqrt{\frac{64}{9}}(\log N)^{\frac 13}(\log\log N)^{\frac 23}}\Big)$ $N$

Procurei informações sobre a pior complexidade possível nesse algoritmo aleatório. No entanto, não consigo localizar informações.

(1) Qual é a pior complexidade da peneira de campo numérico?

(2) Também a aleatoriedade pode ser removida aqui para fornecer um algoritmo subexponencial determinístico?

reference-request derandomization factoring average-case-complexity worst-case
fonte

Respostas:

A peneira de campo numérico nunca foi analisada rigorosamente. A complexidade que você cita é meramente heurística. O único algoritmo subexponencial que foi analisado rigorosamente é o algoritmo de fatoração de Dixon , que é muito semelhante à peneira quadrática. De acordo com a Wikipedia, o algoritmo de Dixon é executado no tempo . O algoritmo de Dixon é randomizado. $e^{O(2\sqrt{2}\sqrt{\log n\log\log n})}$

Todos os algoritmos subexponenciais conhecidos (heuristicamente) requerem randomização. O algoritmo de Dixon precisa encontrar números inteiros modo que seja suave (pode ser fatorado em um produto de primos pequenos) e "aleatório", e a peneira de campo numérico possui requisitos semelhantes, porém mais complicados. O método da curva elíptica precisa encontrar um módulo de curva elíptica cujo módulo de ordem algum fator de seja suave. Nos dois casos, parece difícil derandomizar os algoritmos. $x$ $x^2 \pmod{n}$ $n$ $n$

A complexidade nominal do pior caso de todos esses algoritmos é o infinito: no caso da peneira quadrática e da peneira de campo numérico, você pode sempre gerar o mesmo , enquanto no método da curva elíptica você sempre pode gerar a mesma curva elíptica . Há muitas maneiras de contornar isso, por exemplo, executando um algoritmo de tempo exponencial em paralelo. $x$

Yuval Filmus
fonte

Desde que você tocou no ECM também: conhecemos um algoritmo aleatório de subexp para calcular em usando o ECM em que é desconhecido e randomizado. Você tem uma estimativa de quantos ensaios deste algoritmo é suficiente para obter e onde ?

n! r

$n!r$

O (e x p (\sqrt{\log n}))

$O(exp(\sqrt{\log n}))$

r

$r$

n! r

$n!r$

n! s

$n!s$

(r, s) = 1

$(r,s)=1$

Não tenho idéia do que é , mas de um modo geral, ao escolher parâmetros no ECM, estamos equilibrando entre a probabilidade que a curva seja suficientemente suave e o tempo de execução necessário para testar cada curva. Normalmente, o ponto de equilíbrio é quando . Portanto, o número esperado de tentativas deve ser .

n! r

$n!r$

p

$p$

T

$T$

1 / p \approx T

$1/p \approx T$

O (\exp \sqrt{\log n})

$O(\exp\sqrt{\log n})$

Yuval Filmus

n!

$n!$ é fatorial de . É um problema aberto obter a complexidade linear do fatorial. Sabemos como calcular onde é desconhecido no tempo da subexp. Se conhecermos dois e , podemos obterno tempo de subexpressão se .

n

$n$

n! r

$n!r$

r

$r$

n! r

$n!r$

n! s

$n!s$

(n! r, n! s) = n!

$(n!r,n!s)=n!$

(r, s) = 1

$(r,s)=1$

Lembro-me de calcular um tempo atrás. Eu não acho que poderia melhorar, já que houve um problema e não me lembro dos detalhes.

o último parágrafo parece estranho e pode ser esclarecido mais. você está falando de um cenário em que o RNG está "quebrado" no sentido em que não mostra o espaço geral de distribuição? mas então o paralelismo não ajudaria lá? porque seria o mesmo RNG "quebrado" em paralelo? ou é a ideia de que seria um RNG diferente executado em paralelo? complexidade na verdade paralela de algoritmos de factoring é realmente um assunto completamente diferente complexa, por exemplo, alguns podem ser paralelizado melhor do que outros, big-O pode não ser exatamente o caso, etc

vzn

Nos últimos meses, uma versão da peneira de campo numérico foi analisada rigorosamente: http://www.fields.utoronto.ca/talks/rigorous-analysis-randomized-number-field-sieve-factoring

Basicamente, o pior tempo de execução é incondicionalmente e sob GRH. Isso não é para a peneira de campo numérico "clássico", mas para uma versão ligeiramente modificada, que randomiza mais etapas para facilitar a análise da complexidade. $L_n(1/3, 2.77)$ $L_n(1/3, (64/9)^{1/3})$

Acredito que o artigo correspondente ainda esteja sendo analisado.

Atualização: o artigo está disponível agora. Jonathan D. Lee e Ramarathnam Venkatesan, "Análise rigorosa de uma peneira de campo numérica aleatória", Journal of Number Theory 187 (2018), pp. 92-159, doi: 10.1016 / j.jnt.2017.10.019

djao
fonte

Você pode fornecer uma referência mais completa, onde podemos aprender mais, com título, autor e onde publicados, para que a resposta ainda seja útil, mesmo que o link pare de funcionar?

Como o resultado foi anunciado apenas recentemente, acredito que esteja atualmente em revisão, conforme indicado na minha resposta e, portanto, ainda não publicado. Atualizarei minha resposta no futuro quando houver informações de publicação disponíveis.

djao 18/09/19

FWIW, não parece estar no arxiv.org. No entanto, o autor é Ramarathnam Venkatesan, que pode ajudar em futuras pesquisas, se necessário.

Peter Taylor

Na verdade, é um trabalho de dois autores (JD Lee e R. Venkatesan): cmi.ac.in/activities/…

Sary