Cryptology ePrint Archive: Report 2019/1117

NP-completeness Reduction for Semiprimes Factorization Problem

Yen-Lung Lai

Abstract: We show a reduction of integer (semiprimes) factorization problem to a $NP$-complete problem related to coding. Our results rigorously imply the existence of a quantum computer could possibly devastate existing security system relies on NP-hard problem.

Category / Keywords: applications / Integer Factorization, NP-complete Problems, Complexity Theory

Date: received 29 Sep 2019, withdrawn 3 Oct 2019

Contact author: yenlung lai at monash edu

Available format(s): (-- withdrawn --)

Version: 20191003:061407 (All versions of this report)

Short URL: ia.cr/2019/1117


[ Cryptology ePrint archive ]