| 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 InformationFast Factoring Integers by SVP Algorithms Related ArticlesAmoeba 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 What's a Sample of Size One Worth? Prime Numbers And Primality Testing Travelling Salesman - A Movie About P=NP 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. 
Comments
or email your comment to: comments@i-programmer.info |
| Last Updated ( Wednesday, 10 March 2021 ) |
