Skip to content

A New Factoring Algorithm

April 1, 2009


A new approach to factoring

images20

Lofa Polir is an unknown–until now–undergraduate working for a strong advisor. I do not yet have her picture, nor am I allowed to say any more about her or her advisor. They have sent me a rough draft of her new paper. Her result is nothing less than a new approach to factoring. If correct, it will break factoring based crypto-system in random polynomial time. Amazing. I have been able to get through some of the paper, and at least half seems fine. The last part uses a non-trivial amount of computer calculation plus some deep number theory, and will take a while to check. At this point I say the chances are definitely non-zero that this will all work.

The Claims

The key definition is the following:

Definition: Call an integer {d \times d} matrix {A} a {(p,q,k,d)}-special matrix provided the following are true:

  1. The matrix {A} is invertible modulo {pq};
  2. The matrix {A} is not symmetric modulo {pq};
  3. The matrix {A^{k}} is symmetric modulo {pq};
  4. The matrix {A} satisfies {A^{p} \equiv A \bmod p} and {A^{q} \equiv A \bmod q};
  5. Finally, {k} divides {q-1} and {k} divides {p-2}. (Note, it is important, that these condition are not the same.)

She then claims the following two theorems:

Theorem 1: Suppose that {n=pq} where {p} and {q} are primes. Suppose also that {A} is a {(p,q,k,d)}-special matrix. Then, there is an algorithm that can factor {n} given only {A} and {n}, and it runs in time {\textsf{poly}(\log n,d)}.

Theorem 2: Suppose that {n=pq} where {p} and {q} are primes. Also assume that {k} divides {q-1} and divides {p-2}. There is a random algorithm that given {n},{k} and {d} produces a matrix A in time {\textsf{poly}(\log n,k,d)}. Moreover, with probability at least 1/2 the matrix A is a {(p,q,k,d)}-special matrix.

The second theorem relies on the Generalized Riemann Hypothesis. Clearly, together these theorems yield an attack on {n=pq} based crypto-systems. The attack goes like this. Pick a {k} and “hope” that {k} divides {q-1} and {p-2}. If that is true, then generate matrices and hope that they are (p,q,k,d) -special. If they are, then you can factor n . If they are not try another matrix. Note, even if {k=3} was the only value that worked, then this would break many instances, since {p} and {q} are usually randomly selected.

The first theorem is fairly simple, and I will supply her proof in detail. The second, “proof” is much harder and I have not yet worked through it.

Proof of Theorem 1

Suppose that {A} is a {(p,q,k,d)}-special matrix for {n=pq}. The algorithm is incrediblely simple. Compute the following:

  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}.

She claims that this will factor {n}. More precisely, that one of the greatest common divisor (gcd) calculations will yield a factor of {n}. Clearly, the algorithm runs in the time required; the key question is solely one of correctness.

The key is to look at {M_{p} = M \bmod p} and also {M_{q} = M \bmod q}. Let’s look at {M_{p}}. By definition this is equal to {A^{pq-1} \bmod p}. By the definition of special, {M_{p}} is equal to {A^{q-1} \bmod p}. Again by the definition of special, {k} divides {q-1}. Then, {M_{p}} is equal to

\displaystyle  (A^{k})^{\frac {q-1} k} \bmod p

and so {M_{p}} is equal to a symmetric matrix modulo {p}. Note, while the product of symmetric matrices are not always symmetric, they are if they commute. Since powers of any matrix commute with each other, {M_{p}} equals a symmetric matrix modulo {p}.

What happens to {M_{q}}? The trick is that it is not a symmetric matrix. We see why in a moment. But, for now assume that was true. Then, there must be {i \not = j} so that {M_{q}} entries at {(i,j)} and {(j,i)} are different. Then, by the Chinese Remainder Theorem {M_{ij} - M_{ji}} will be divisible by {p} but not by {q}. This shows that the algorithm factors {n}.

Thus, the key question is why is {M_{q}} not a symmetric matrix modulo {q}. As before {M_{q}} is equal to {A^{p-1} \bmod q}. But again by the definition of special, {p-1 = kl+1} for some {l}. Then, {M_{q}} is equal to

\displaystyle  A \cdot (A^{k})^{\frac {p-2} k} \bmod q.

Thus, {M_{q}} is {A \cdot S \bmod q} where again {S} is symmetric. Since {A} was assumed to not be symmetric the following simple lemma finishes the argument.

Lemma 4 Suppose that {X} and {Y} are square matrices of the same dimension. Suppose that they commute and that {Y} and {X \cdot Y} are both symmetric. Also suppose that {Y} is invertible. Then, {X} is also symmetric.

Proof: The transpose of a matrix {M} is denoted by {M^{T}}. Recall that by a standard fact about transpose, {(X \cdot Y)^{T} = Y^{T} \cdot X^{T}} for any matrices {X} and {Y}. Now,

\displaystyle (X \cdot Y)^{T}	 = Y^{T} \cdot X^{T} = Y \cdot X^{T}.

The last uses that {Y} is symmetric. Now since {X \cdot Y} is symmetric it also follows that

\displaystyle  (X \cdot Y)^{T}	 = X \cdot Y = Y \cdot X.

The last step uses that {X} and {Y} commute. Thus, it follows that {Y \cdot X^{T} = Y \cdot X}. Finally, {Y} is invertible so that {X^{T} = X}. \Box

“Proof” of Theorem 2

This is the part of her paper that I least understand. She needs to construct a {(p,q,k,d)}-special matrix {A} given only {n=pq} and {k} and {d}. She only shows any details for the special case {k=3} and {d=4}. As state earlier, even this restricted case, would break many instances of systems that use randomly generated {p} and {q}.

Her approach to theorem 2 is to write down the formal equations that define the properties of {A} being a special matrix. The main ones that she has to worry about are that {A} must not be symmetric and yet {A^{k}} is symmetric modulo {n}. The Fermat conditions: the matrix {A} satisfies {A^{p} \equiv A \bmod p} and {A^{q} \equiv A \bmod q} are handled by an indirect argument.

The formal system is a set of equations in {16} unknowns and {7} equations. One equation is used to force the matrix not to be symmetric and {6} equations are used to make the power {A^{3}} symmetric. These are, of course, non-linear equations modulo {n}. In general such equations are equivalent to factoring. However, there is special structure in her equations that she exploits.

After some Gröbner basis argument she reduces the solvability of these equations to the solvability of one high degree equation in two unknowns modulo n . Then, she uses a Pollard-Schnorr type descent argument to prove that with high probability this equation has a solution.

The problem with checking this is first the Gröbner basis step involves a fair amount of equation manipulation, which needs to be checked carefully. Also the descent argument is a clever variation of the famous one due to John Pollard and Claus Schnorr and seems plausible, but again must be carefully checked.

Open Problems

The obvious open problem is: does her proof work? A potentially exciting time. I will get back soon with more details.

About these ads
12 Comments leave one →
  1. april fool permalink
    April 1, 2009 7:55 am

    happy april fools day :)

  2. April 1, 2009 8:31 am

    This is why blogs are so great! How else would such front-line information ever spread so fast to those who are interested in this kind of topics?!

  3. April 1, 2009 8:32 am

    … but then, it’s April 1st! :-)

  4. April 1, 2009 9:13 am

    Lofa Polir == aPril fooL

  5. Dave permalink
    April 1, 2009 9:16 am

    Can someone with more linear algebra experience tell me if there is a joke contained in the “proof” as well?

  6. kintali permalink
    April 1, 2009 12:16 pm

    I read your post through Google Reader and reached for a pen and paper to understand the theorems, (as I did with your previous posts) and then I saw the comments :) Every year I forget April fools day and always fall for the first prank :(

  7. williamhuang permalink
    April 1, 2009 8:35 pm

    “Every year I forget April fools day and always fall for the first prank :(” so do I.

  8. conglac2009 permalink
    April 2, 2009 9:44 am

    I thought this was going to be better but so far it is very very stupid whats the point of it anyway?

    • rjlipton permalink*
      April 2, 2009 9:59 am

      I will explain. In the next post I will show that this had a real point…rjlipton

  9. Craig permalink
    January 26, 2011 5:51 pm

    Man, old post I know, but still entertaining reading.

    It might have been a stronger case for factoring against cryptosystems if it weren’t so easily defeated by making p and p-2 twin primes. Then k would not factor p-2 and you couldn’t build a matrix. I got about as far as you mentioned p-2. Then I looked down to see if anybody else had figured it out.

    Teaches me to look more closely at people’s names! Haha!

Trackbacks

  1. Top Posts « WordPress.com
  2. Wait Wait… Don’t Fool Me! | Gödel's Lost Letter and P=NP

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 1,764 other followers