Factoring Again: No Joking
A new approach to factoring?
Lofa Polir is not a real person. She did not solve factoring. She does not exist. Her name is an an anagram for “April Fool”. I hope you enjoyed the joke. While 99% of my posts are serious, I hope that it is okay to liven things up now and again. I apologize if that bothered you. As an aside, here is a great site for making and breaking anagrams.
The real joke may however be on me. The approach I sketched in the last post is not a complete joke. Apparently many of you saw that “Lofa Polir” equals “April Fool” and immediately stopped reading. However, the method I outlined is a possible approach to factoring. Really. Today is April , and all jokes are over.
The first theorem that I stated and proved is correct. If you can find a special, in the sense defined there, matrix , then the following simple algorithm does indeed factor :
- Compute ;
- Then, compute the gcd’s of and for all .
One of these greatest common divisor calculations will yield a factor of .
Thus, if you want to factor and there is a special matrix , then you can factor. Note, the factor algorithm uses a kind of Fermat Little Theorem for matrices. The open question is could such matrices exist? The answer is I do not know. So the “April Fool” post is only a half joke. The first theorem is true.
The difficulty is with the construction of a special matrix. The second theorem is not proved: I have no idea how to construct the special matrix . So at this time the gap in the method is whether or not we can find the needed matrices . The last laugh could be on me if someone figures out how to construct such matrices. In that case do I get a reference? A thank you?
The philosophy of this approach is simple: Find a matrix so that its powers behavior differently modulo than . In the definition of special, we assumed that modulo one prime was symmetric and modulo the other was asymmetric. Any reasonable difference would allow the method to work. I plan in a future post to go into the details of this approach. Not right away–I will let the joke atmosphere go away first.
One last point, I mentioned a result due to John Pollard and Claus Schnorr from 1984. They proved the following beautiful result:
Theorem 1 The equation
in and is solvable in polynomial time provided and are both not modulo .
The Pollard-Schnorr Theorem holds for composite: this is the big surprise. Usually solving equations over composites is equivalent to factoring. For example, it is critical that not be modulo , since solving
can be easily shown to be equivalent to factoring. I plan to discuss this and related theorems in a future post.
NSF and Factoring
When Peter Freeman was the AD at NSF, I was on the NSF CISE advisory board. One meeting we broke up into small groups to discuss ideas for future computing initiatives for NSF. I was selected by my subgroup to make a report to the rest of the board–about thirty top computer scientists from all fields. I decided to have a bit of fun to make the point that factoring could be easy:
I asked, did any of you read John Markoff’s New York Times article this morning? No one said that they had. I went on and said that his article reported that a senior at the Bronx High School of Science in New York City had found a new algorithm for factoring. She has implemented it and is using it to factor ten thousand digit numbers in minutes with just her laptop. Experts think that her method could be a polynomial time algorithm, although that is not yet clear
I then stopped talking. No one in the room jumped up and yelled “liar”. No one seemed too surprised. No one disputed the story. I then confessed that it was all made up. But my point was that factoring could be easy, and NSF should think about putting money into it and related questions. I am not sure that any of them got my point. One, during the next coffee break, said he was not worried, since he was sure that Times had just gotten the story wrong.
Is Factoring Easy?
As you may have guessed, I have thought about factoring for years. Perhaps too many years. But, I really believe that it is likely to be “easy”. I have several reasons why I believe this:
The first reason is due to Michael Rabin. I am not sure if he shares all my views completely, but I believe that Michael has his doubts. For example, the running time of the current best factoring algorithm, the general number field sieve, is:
where . Michael has pointed out to me, on a number of occasions, that if was reduced from , then there would be about an fold increase in the size of numbers that could be factored. What would happen if was reduced to : you see the point. Even without getting a polynomial time algorithm, it could be the case that factoring is for all practical purposes too easy to use for crypto-systems.
The second reason is based on complexity theory. Since factoring is not NP-complete, nor is it complete for any other natural class, there seems that are no dire consequences to a polynomial time algorithm for factoring. Yes such an algorithm would in principle break many crypto-systems, but there would be no collapses of known complexity classes. This is completely different from the consequences of a polynomial time algorithm for SAT, for example.
The third reason is the lack of radical approaches to factoring. The reason I choose to show you the matrix approach was to show that there could be new ways to attack factoring. I believe that all the current approaches to factoring, even the number field sieve, are very similar. Perhaps there are other radically new ways to attack factoring. In my post on Legendre, I pointed out that computing fast would also factor. Are there are approaches?
The next reason is that factoring is a special problem. It not only seems to be hard, but it seems to be easy to create hard instances. This is not true for most problems that we believe are hard. We think that selecting two random primes and yields an intractable problem: find the factors of . This special property is the basis of many wonderful methods in modern cryptography. Some of them seem like “magic”. The ability to have a public-key system, to sign documents, to do “zero-knowledge proofs”, and so on. I ask you which is more surprising these wonderful results or the existence of a factoring algorithm? I will definitely do a long post on this point in the future.
The last reason, is as I keep pointing out and will again, conventional wisdom is often wrong. The conventional wisdom on factoring is that it is hard. Perhaps this is not true. A couple of years ago, while on a panel at a conference, Adi Shamir stated that he thought that public-key crypto-systems would be broken in the next decade. He based this on the terrific work that the Chinese have already done in breaking hash functions. We’ll see.
The main problem is of course: what is the complexity of factoring? A more approachable question is can we show that the matrix based method that I outlined cannot succeed? That is can you prove that there are no such matrices? Or can you use the matrix idea to get a better factoring algorithm. Note, you do not need to get polynomial time, just beat the current best method.