Factorizing RSA keys: an improved analogue solution

Journal article

Factorization is notoriously difficult. Though the problem is not known to be NP-hard, neither efficient, algorithmic solution nor technologically practicable, quantum-computer solution has been found. This apparent complexity, which renders infeasible the factorization of sufficiently large values, makes secure the RSA cryptographic system.

Given the lack of a practicable factorization system from algorithmic or quantum-computing models, we ask whether efficient solution exists elsewhere; this motivates the analogue system presented here. The system's complexity is prohibitive of its factorizing arbitrary, natural numbers, though the problem is mitigated when factorizing n = pq for primes p and q of similar size, and hence when factorizing RSA keys.

Ultimately, though, we argue that the system's polynomial time and space complexities are testament not to its power, but to the inadequacy of traditional, Turing-machine-based complexity theory; we propose precision complexity (defined in our previous paper) as a more relevant measure.

Authors: Blakey, E

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Springer
• DOI: 10.1007/978-4-431-88981-6_2
• Language: English
• Keywords: complexity; analogue; factorization; cryptography
• Subjects: Computer science (mathematics)