Adicionar números inteiros representados por sua fatoração é tão difícil quanto fatorar? Solicitação de referência

Estou procurando uma referência para o seguinte resultado:

Adicionar dois números inteiros na representação fatorada é tão difícil quanto fatorar dois números inteiros na representação binária usual.

(Tenho certeza de que está lá fora, porque isso é algo que eu já tinha pensado em algum momento e fiquei emocionado quando finalmente o vi impresso).

"Adição de dois inteiros na representação factorizada" é o problema: dadas as fatorações primos de dois números $x$ e $y$ , a saída Fatorização primo de $x+y$ . Observe que o algoritmo ingênuo para esse problema usa fatoração na representação binária padrão como uma sub-rotina.

Atualização : Obrigado Kaveh e Sadeq pelas provas. Obviamente, quanto mais provas, melhor, mas eu também gostaria de incentivar mais ajuda para encontrar uma referência , que, como eu disse, tenho quase certeza de que existe. Lembro-me de lê-lo em um artigo com outras idéias interessantes e pouco discutidas, mas não lembro quais eram essas outras idéias ou sobre o que era o jornal em geral.

Suponha que possamos resolver o problema (vamos chamá-lo FactSum) na classe de complexidade e C é fechado sob log -iteration (aka log recursão -bounded) (por exemplo, se podemos calcular x * y , onde * é uma função binária, podemos calculado x 1 ∗ … ∗ x log n ) e contém P (esta última condição pode ser mais fraca). Mostramos que factoring é também no C .$C$$C$$\log$$\log$$x*y$$*$$x_1*\ldots*x_{\log{n}}$$\mathsf{P}$$C$

Observe que cada número pode ser escrito como uma soma das potências de 2 . Cada um deles é fácil de fatorar.$\log n$$2$

Agora, forneça um número, escreva-o como a soma dos poderes dele, depois escreva cada somamand na representação de fatoração e use o algoritmo para somar na representação de fatoração. O resultado será a fatoração do número de entrada.

Isso mostra que o fatoramento é redutível à identificação de do seu problema FactSum. Portanto, o fatoração está em P FactSum (e acho que P pode ser substituído por N C 1 aqui).$\log$$\mathsf{P}^{\text{FactSum}}$$\mathsf{P}$$\mathsf{NC^1}$

Não tenho conhecimento de uma referência, mas acho que criei uma prova:

Suponha que você tenha um oráculo que, ao inserir dois números fatorados$\mathcal{O}$

$x = \prod_{i=1}^n p_i^{\alpha_i}$

e

$y = \prod_{i=1}^m q_i^{\beta_i} \enspace$,

produz a fatoração de .$x+y$

Tendo acesso a , podemos fatorar qualquer número N no tempo polinomial usando o seguinte procedimento recursivo.$\mathcal{O}$$N$

Fator de procedimento ( )$N$

1. Encontre um primo tal que N / 2 ≤ x ≤ N - 1 e deixe y = N - x .$x$$N/2 \le x \le N-1$$y = N - x$
2. Se não for primo, obtenha a fatoração de y pelo fator de chamada recursiva ( y ) e produza O ( x , f a c t ou r ( y ) ) .$y$$y$$y$$\mathcal{O}(x, factor(y))$
3. Outra saída .$\mathcal{O}(x,y)$

Análise:

Pelo teorema dos números primos para grande o suficiente , há muitos primos entre N / 2 e N - 1 . Se N for tão pequeno que nenhum prime caia nesse intervalo, você pode fatorar N facilmente. Portanto, a etapa 1 passa.$N$$N/2$$N-1$$N$$N$

Na etapa 2, você pode usar o AKS ou qualquer outro teste de primalidade em tempo polinomial.

O número de recursão é simplesmente , pois a cada passo N é cortado pela metade (pelo menos)$O(\lg(N)) = O(|N|)$$N$

PS-1: Assumir a conjectura de Goldbach pode ajudar a acelerar o procedimento para números pares (e possivelmente ímpares).

PS-2: A redução usada é uma redução de Cook. Alguém pode estar interessado em realizar a prova usando reduções de Karp.

Esta resposta é independente da minha resposta anterior . Seu objetivo é abordar a preocupação de @ Kaveh nos comentários:

É fácil de fazer se queríamos números, mas eu não vejo como fazê-lo, mesmo com log log n números.$\log n$$\log \log n$

Eu tinha uma preocupação semelhante:

A redução usada é uma redução de Cook. Alguém pode estar interessado em realizar a prova usando reduções de Karp.

(As reduções de Karp são para problemas de decisão. Aqui, por redução de Karp, quero dizer uma redução de Cook de consulta única. Desculpe pela terminologia não padrão!)

A resposta abaixo é baseada nas discussões aqui: /math/54580/factoring-some-integer-in-the-given-interval .

Nesta resposta, fornecerei uma redução determinística de Karp em tempo polinimial, de fatoração para fatoração, a soma de dois números inteiros representados por suas fatorações . Porém, há um problema: no decorrer da prova, usarei a seguinte suposição da teoria dos números:

$p_n$$p_{n+1}$$p_{n+1} - p_n = O(\log^2p_n)$

$N$$n=|N|=O(\log N)$$N$$[N - \log^3N, N]$$\log^3N = O(n^3)$

Let $x$ be the prime number in $[N - \log^3N, N]$, and let $y=N-x$.

Since $0 \le y \le \log^3N$, we have $|y| = O(\log \log N) = O(\log n)$, and $y$ can be easily factorized (say, using trial division).

Finally, submit $(x,y)$ along with their factorizations to the oracle, and get the factorization of $N = x+y$.