A German cryptographic researcher, Dr. Claus Peter Schnoor, has published a paper on the website of The International Association for Cryptologic Research that describes a new classical method of factoring large integers based upon a SVP (Shortest Vector Problem) algorithm. He indicates that this would be much faster than the previously known classical algorithms known as quadratic sieve and number field sieve. The paper estimates that a 400 bit binary number could be factor in 4.2×109 arithmetic operations while an 800 bit number could be factor in 8.4×1010 arithmetic operations. The largest known factoring successfully computed so far has been a 829 bit number, known as RSA-250, that required 2700 CPU core years  using 2.1Ghz Intel Xeon Gold 6130 CPUs.

Such an algorithm, if it really works, would be competitive with Shor’s famous quantum factoring algorithm which woke many people up to the potential for use and misuse of quantum technology. This is because the common technology used on the internet for encrypting keys could be broken if one had an efficient means of factoring a 2048 bit number. The cryptologic community is now studying the paper and is not clear if the proposed technique really works. Sometimes a paper is published or an algorithm developed that claims to have successfully accomplished something, but later on a hidden flaw is found in the logic and what was claimed doesn’t really work after all. But if the algorithm does indeed work and is successfully implemented by somebody, it would trigger a rush in the IT world to convert encryption methods for key distribution to either Quantum Key Distribution (QKD) technology or the newer PQC algorithms that are not based upon factoring large numbers. You can view the paper by clicking here.

March 6, 2021