Factorization In P - This Destroys RSA
Wednesday, 10 March 2021

A recent, and on-going, kerfuffle on the Internet is the claim and dispute that the task of factoring is achievable in polynomial time. If this were true it would compromise the most commonly used public key crypto system and render the need for quantum computers null and void.

OK, my last comment is slightly tongue-in-cheek; I know that quantum computers might have other applications, but the dream of code cracking is what keeps people up at night.

This is an interesting story because it might be true and it illustrates everything that is wrong in the world of mathematics at the current time.


A short time ago a preprint, not peer reviewed, appeared with the provocative line "This destroys the RSA cryptosystem". Given the importance of RSA, this is something that draws attention and presumably this is why it is at the start of an otherwise dense and difficult-to-read paper. Normally this sort of paper would be mostly ignored but, as well as the provokative statemen,t it isn't by an unknown presumed crank, it is by the well-regarded, but retired, crypgrapher, Claus Peter Schnorr.

The paper describes a development on an idea that he has been working on for some time - a particular approach to factoring via a lattice-based algorithm. The key statement in the abstract is:

"We factor N ≈ 2 400 by n = 47 and N ≈ 2 800 by n = 95. Our accelerated strong primal-dual reduction of [GN08] factors integers N ≈ 2 400 and N ≈ 2 800 by 4.2 · 109 and 8.4 · 1010 arithmetic operations, much faster then the quadratic sieve QS and the number field sieve NFS and using much smaller primes pn. This destroys the RSA cryptosystem."

The important thing is to notice that doubling the size of the integer exponent from 400 to 800 only increases the number of operations from 109 to 1010 - the algorithm isn't exponential and the paper "proves" that it is polynomial. 

At this point you might be thinking "this is a problem long thought to be in NP, but now shown to be in P - doesn't this prove that P=NP?" If it did then this would be a bigger deal than just destroying RSA. It would be the biggest breakthrough in computer science theory for a long while. Unfortunately, it doesn't prove that P=NP as factoring has never been proven to be NP-complete. If you can prove that any NP-complete problem is in P, then you have proved that all NP problems are in P. Factoring has long been suspected of not being NP-complete, but who knows.

And who knows if this proof is indeed a proof. The paper is very dense and there are no practical examples included. If there were the matter would be settled. There are some nice big numbers that are the product of two primes just waiting for someone to work out what the primes are and this still has not been done. These test cases are like the cannary in the cage testing for gas - and the canary is still very much stuck to its perch.

OK, you can argue that it is not theory's job to implement practical results ?? and the paper does claim to prove the assertions. However, this is a current problem with mathematics.The current style of mathematical papers is to make little or no concession to understanding. The theorems and proofs are simply listed and you get the general impression that no effort goes into making the argument understandable. In fact, you get the impression that anything that obfuscates only serves to make the author look better and more academic in writing a paper you can't understand. Long gone are the days when a reasonably well-read mathematician in one area can hope to read a paper in another and understand. Indeed even mathematician in the area concerned often have little hope of understanding. The incidence of mathematicians claiming to have proved something and leaving it to others to untangle their presentations seems to be on the increase, for example Shinichi Mochizuki.

What are the chances that the paper is correct?

Not good. It is still being worked over, but a post on Twitter by Keegan Ryan makes it look as if there is a simple flaw. Of course, there might not be...




More Information

Fast Factoring Integers by SVP Algorithms

Related Articles

The Machine In The Ghost       

Public Key Encryption

Amoeba Solves Traveling Salesman Problem

Search For Twin Prime Proof Slows       

A Mathematical Proof Too Long To Check - The Erdos Discrepancy Conjecture       

Six Degrees Of Separation Is New

Finding Solutions To Diophantine Equations By Smell

48th Mersenne Prime Computed

What's a Sample of Size One Worth?

Prime Numbers And Primality Testing

Travelling Salesman - A Movie About P=NP

Erdos Conjecture Proven

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.



The University of Tübingen's Self-Driving Cars Course

The recorded lectures and the written material of a course on Self-Driving Cars at the University of Tübingen have been made available for free. It's a first class opportunity to learn the in an [ ... ]

ACM Adopts Open Access Publishing Model

ACM, the Association for Computing Machinery, the professional body for computer scientists, has relaunched Communications of the ACM, the organization’s flagship magazine, as a web-first  [ ... ]

More News

raspberry pi books



or email your comment to: comments@i-programmer.info

Last Updated ( Wednesday, 10 March 2021 )