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 ${3^{rd}}$, 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 ${A}$, then the following simple algorithm does indeed factor ${n=pq}$:

1. Compute ${M=A^{n-1} \bmod n}$;
2. Then, compute the gcd’s of ${n}$ and ${M_{ij}-M_{ji}}$ for all ${i \not = j}$.

One of these greatest common divisor calculations will yield a factor of ${n}$.

Thus, if you want to factor ${n=pq}$ and there is a special matrix ${A}$, 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 ${A}$. So at this time the gap in the method is whether or not we can find the needed matrices ${A}$. 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 ${A}$ so that its powers behavior differently modulo ${p}$ than ${q}$. In the definition of special, we assumed that ${A^{n}}$ 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

$\displaystyle x^{2} + ay^{2} \equiv b \bmod n$

in ${x}$ and ${y}$ is solvable in polynomial time provided ${a}$ and ${b}$ are both not ${0}$ modulo ${n}$.

The Pollard-Schnorr Theorem holds for ${n}$ composite: this is the big surprise. Usually solving equations over composites is equivalent to factoring. For example, it is critical that ${a,b}$ not be ${0}$ modulo ${n}$, since solving

$\displaystyle x^{2} \equiv b \bmod n$

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 ${\dots}$

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:

${\bullet}$ 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:

$\displaystyle \exp \big( c (\ln n)^{1/3} (\ln \ln n)^{2/3}\big)$

where ${c \approx 2}$. Michael has pointed out to me, on a number of occasions, that if ${c}$ was reduced from ${2 \rightarrow 1}$, then there would be about an ${8}$ fold increase in the size of numbers that could be factored. What would happen if ${c}$ was reduced to ${1/100}$: 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.

${\bullet}$ 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.

${\bullet}$ 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 ${k! \bmod n}$ fast would also factor. Are there are approaches?

${\bullet}$ 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 ${p}$ and ${q}$ yields an intractable problem: find the factors of ${n=pq}$. 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.

${\bullet}$ 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.

Open Problems

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.

April 3, 2009 6:07 pm

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 {p} and {q} yields an intractable problem: find the factors of {n=pq}. 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?

Neither the hard-on-average property nor the ability to construct “crypto magic” are contingent on factoring in particular. In fact, average-case cryptographic hardness and zero-knowledge proofs are implied by even weaker assumptions than factoring (one-way functions).

Do you think all cryptographic assumptions are unlikely to be true?

April 3, 2009 6:19 pm

Not clear. But most would agree that factoring is among the very few hard problems that seem to really have a good method of generating hard instances. Much harder problems, like SAT, we have no good method of generating hard instances.

2. April 5, 2009 10:01 pm

question: is there some simple means of computing the k?
I’m a wee bit rusty with my computational number theory (despite having played with such quite a bit when I at Bronx Science around 02-06 :p)

April 7, 2009 7:10 am

Much harder problems, like SAT, we have no good method of generating hard instances.

We seem to have a perfectly good method of generating a hard instance of SAT – take a random 3SAT formula F of n variables and m clauses for, say, m = 100n (perhaps m=n^{1.49} will do as well). While with high probability F will not be satisfiable, we do not know of any polynomial-time refutation algorithm A that outputs “unsatisfiable” with probability > 2/3 on such F, but never outputs “unsatisfiable” on a satisfiable formula.

For approximating linear equations modulo 2 (i.e., parity with noise) again it seems that random noisy equations are a hard instance. (This time, it’s easy to also find a hard distribution on YES instances, that have a solution.)

The planted clique distribution seems also to be a way to generate hard instance for clique/independent sets.

In fact, for many hard problems we do know a way to generate seemingly hard instances. The well known exceptions are graph isomorphism and unique games, but then again, many people are not sure these problems are really hard.

In contrast, I would say that the existence of a challenge hard distribution is one of the best arguments why factoring may be hard. The reason is that it’s often much easier to find an algorithm for a particular input distribution, in particular it seems it would be easier to find a heuristic that seems to succeed experimentally, without any proof of correctness. The fact that such a heuristic was not found (despite significant effort) may seem to indicate that it does not exist.

(I have no idea if factoring is easy or hard – if forced to bet I’d say it’s hard for the reason above, but would not be super-shocked – just super-excited – if a polynomial-time algorithm was found.)

–Boaz

4. April 10, 2009 12:45 pm

I read your article on factoring and I found it very interesting. Your way (and Scott Aaronson’s) to present things makes them understandable to many of us who lack the mathematical tools required to do so. I will be coming back to this blog to read and re-read your articles.

thanks again

April 10, 2009 12:53 pm

Thanks for you kind comment. I am trying to make this accessible to many at different levels, glad seems to be working.

5. April 11, 2009 11:39 am

I always thought that you cannot solve a diophantine equation without first factoring a number so I am not sure I understand how John Pollard and Claus Schnor’s theorem can get around that. (Usually, when solving diophantine eqs, we end up with something like (x-a)*(y-b)=N. Clearly, N needs to be factored before we can solve for x and y).
Because if there is a way to solve their equation without factoring the number it represents, then factoring is easy.

Can you please comment on this?

regards

6. October 7, 2010 8:53 am

Hi rjlipton

I really agree with you. Great to see someone who’s is standing up for different approaches. Also believe in the easiness of factorization.