Ajouter des entiers représentés par leur factorisation est aussi difficile que la factorisation? Demande de réference

Je recherche une référence pour le résultat suivant:

Ajouter deux entiers dans la représentation factorisée est aussi difficile que factoriser deux entiers dans la représentation binaire habituelle.

(Je suis presque sûr que c'est là-bas parce que c'est quelque chose que je me demandais à un moment donné, puis j'étais excité quand je l'ai finalement vu sur papier.)

"Ajouter deux entiers dans la représentation factorisée" est le problème: étant donné les factorisations premières de deux nombres et y , produire la factorisation première de x + y . Notez que l'algorithme naïf de ce problème utilise la factorisation dans la représentation binaire standard comme sous-programme.$x$$y$$x+y$

Mise à jour : Merci Kaveh et Sadeq pour les preuves. Évidemment, plus il y a de preuves, plus on est de fous, mais j'aimerais aussi encourager plus d'aide à trouver une référence , qui, comme je l'ai dit, j'en suis assez sûr. Je me souviens l'avoir lu dans un document contenant d'autres idées intéressantes et rarement discutées, mais je ne me souviens pas de ce qu'étaient ces autres idées ni de l'objet du document en général.

Supposons que nous pouvons résoudre le problème (appelons-le FactSum) dans la classe de complexité et C est fermé sous log -iteration (aka récursion log- bornée) (par exemple, si nous pouvons calculer x ∗ y où ∗ est une fonction binaire, nous pouvons calculé x 1 ∗ … ∗ x log n ) et contient P (cette dernière condition peut être affaiblie). Nous montrons que l' affacturage est également en C .$C$$C$$\log$$\log$$x*y$$*$$x_1*\ldots*x_{\log{n}}$$\mathsf{P}$$C$

Notez que chaque nombre peut être écrit comme une somme de puissances de 2 . Chacun d'eux est facile à prendre en compte.$\log n$$2$

Maintenant donné un nombre, écrivez-le comme la somme de ses puissances, puis écrivez chaque somme dans la représentation d'affacturage, puis utilisez l'algorithme pour les additionner dans la représentation d'affacturage. Le résultat sera la factorisation du numéro d'entrée.

Cela montre que l'affacturage est réductible à la de votre problème FactSum. L'affacturage est donc dans P FactSum (et je pense que P peut être remplacé par N C 1 ici).$\log$$\mathsf{P}^{\text{FactSum}}$$\mathsf{P}$$\mathsf{NC^1}$

Je ne connais pas de référence, mais je pense avoir trouvé une preuve:

Supposons que vous ayez un oracle qui, en entrée, deux nombres factorisés$\mathcal{O}$

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

et

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

renvoie la factorisation de .$x+y$

Ayant accès à , nous pouvons factoriser n'importe quel nombre N en temps polynomial en utilisant la procédure récursive suivante.$\mathcal{O}$$N$

Facteur PROCÉDURE ( )$N$

1. Trouvez un nombre premier tel que N / 2 ≤ x ≤ N - 1 , et soit y = N - x .$x$$N/2 \le x \le N-1$$y = N - x$
2. Si n'est pas un nombre premier, obtenez la factorisation de y par le facteur d'appel récursif ( y ) et la sortie O ( x , f a c t o r ( y ) ) .$y$$y$$y$$\mathcal{O}(x, factor(y))$
3. Sinon, sortie .$\mathcal{O}(x,y)$

Une analyse:

Par théorème des nombres premiers pour assez grand , il y a beaucoup de nombres premiers entre N / 2 et N - 1 . Si N est si petit qu'aucun nombre premier ne tombe dans cet intervalle, vous pouvez facilement factoriser N. Par conséquent, l'étape 1 passe.$N$$N/2$$N-1$$N$$N$

À l'étape 2, vous pouvez utiliser AKS ou tout autre test de primalité en temps polynomial.

Le nombre de récursivité est simplement , car à chaque étape N est coupé de moitié (au moins)$O(\lg(N)) = O(|N|)$$N$

PS-1: En supposant que la conjecture de Goldbach pourrait aider à accélérer la procédure pour les entiers pairs (et éventuellement impairs).

PS-2: La réduction utilisée est une réduction Cook. On pourrait être intéressé à effectuer la preuve en utilisant des réductions de Karp.

Cette réponse est indépendante de ma réponse précédente . Son objectif est de répondre aux préoccupations de @ Kaveh dans les commentaires:

C'est facile à faire si nous voulions numéros de log n , mais je ne vois pas comment le faire même avec des numéros de log n .$\log n$$\log \log n$

J'avais une préoccupation similaire:

La réduction utilisée est une réduction Cook. On pourrait être intéressé à effectuer la preuve en utilisant des réductions de Karp.

(Les réductions Karp sont pour des problèmes de décision. Ici, par réduction Karp, je veux dire une réduction Cook à une seule requête. Désolé pour la terminologie non standard!)

La réponse ci-dessous est basée sur les discussions ici: /math/54580/factoring-some-integer-in-the-given-interval .

Dans cette réponse, je fournirai une réduction déterministe du temps polynimial de Karp de la factorisation à la factorisation de la somme de deux entiers représentés par leurs factorisations . Il y a cependant un hic: au cours de la preuve, je vais utiliser l'hypothèse théorique des nombres suivante:

$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)$

$x$$[N - \log^3N, N]$$y=N-x$

$0 \le y \le \log^3N$$|y| = O(\log \log N) = O(\log n)$$y$

$(x,y)$$N = x+y$