Si est en fait égal à , comment cela améliorerait-il nos algorithmes pour factoriser les entiers plus rapidement. En d'autres termes, quel genre d'information cela nous donnerait-il pour mieux comprendre la factorisation des nombres entiers?
Si , et que nous avons un algorithme qui peut résoudre le problème k-SAT en temps polynomial, la factorisation entière peut simplement être réduite à k-SAT en décrivant l'affacturage comme un problème dans k-SAT.
Essentiellement, cela fonctionne comme suit: Vous créez un tas de variables représentant chacune les bits de , et q , et n . Ensuite, vous formulez le problème k-SAT comme p ∗ q = n . Puisque n est connu, vous pouvez définir ces valeurs. Ensuite, une affectation satisfaisante décrira un p et un q valides . Pour décrire la multiplication dans k-SAT, vous pouvez utiliser n'importe lequel des algorithmes de multiplication connus et décrire son circuit logique dans k-SAT. Pour plus d'informations sur la réduction de l'affacturage en k-SAT, voir ici .
Quant à mieux comprendre l'affacturage, cela nécessiterait probablement plus de recherches et d'analyser l'algorithme magique (qui peut résoudre des problèmes NP-complets en temps polynomial déterministe), et peut-être le spécialiser dans la formulation d'affacturage entier du problème k-SAT (qui a évidemment une structure très spécifique, en fonction de l'algorithme de multiplication utilisé).
Le problème de décision pour l'affacturage est et l'affacturage peut y être réduit en temps polynomial déterministe.
Si alors tout problème dans N P, y compris la factorisation, aura un algorithme de temps polynomial.
Notez que les algorithmes déterministes / probabilistes les plus connus pour la factorisation en ce moment prennent un temps exponentiel donc un algorithme de temps polynomial serait une grande amélioration. Pour vous en faire une idée, pensez à factoriser un nombre de 2000 bits. L'une peut prendre plus de temps que jamais depuis le big bang, l'autre peut répondre en quelques millisecondes.