Mathematical tomfoolery: factoring as a geometric problem

RSA encryption… it’s really that easy.

So I’ve always been fascinated by the problem taking a number n = pq and trying to factor it efficiently. While there is a good reason this is worth working on – RSA public key cryptography is dependent on the difficulty of this – I originally just found it fascinating: it seemed that all of the information about the factorization must be somehow contained in n. Simply becausewhen you multiply the factors together no information is lost.

Here’s a way to think about it, let’s say p and q are prime numbers, and let n = pq. Now, if we had any loss of information, then factoring n completely would provide more than one answer. However, that is impossible, however I will leave the exercise of proving that any factorization of n is unique to the reader.

The only information I can see that is lost is the ordering, and that is really insignificant to the original problem – what did I multiply together to produce n.

While playing with this, I keep on finding interesting things to play with. Obviously I haven’t “solved” the problem; otherwise I’d be doing my PhD at UofT. This lack of progress is not surprising considering this is a difficult problem people have been working on for centuries.

I have many many pages of notes, and so, I decided, screw it, I will just share these on my blog and maybe someone will have an idea that pushes me a bit further. Heck, maybe a professor of math will see it and invite me to do my PhD with them around this.

Each idea really deserves it’s own summary post, so I will start with the first approach I’ve played with for the longest.

Solving factoring is solving a simple diophantine equation.

I’m going to distill hundreds of pages of notes into the following, this is the tip of the iceberg when it comes to interesting results from this method. If there is a piece you want me to expound further on, let me know. If I find a particular theorem work going through I will post it in a later post.

The whole idea behind this is the following proposition:

Given, n = pq, p,q \in \mathbb{P}, p,q > 2

It is true that n = (l-k)(l+k) = l^2-k^2, l,k \in \mathbb{N}

where l \neq (n+1)/2, p= (l-k), q=(l+k)

Thus, given an n where we know n = pq: p,q odd, then we can easily see that l = (p+q)/2, and k=l-p, for p<q

Hence p=l-k, q= l+k. So now you just have to solve for l and k. This is a whole lot harder than it sounds. In fact it’s really just one step away from a Heronian triangle; A triangle where all sides are integers. In fact, this leads to an easy proof for finding Heronian triangles, but I will leave that to the reader.

In short, this problem reduces to solving the following diophantine equation.

l^2 = n + k^2

For the more geometrically minded, this means factoring is solving the following diagram for l,k \in \mathbb{N}.

Geometric Representation for Factoring (© 2013 kjro.se)

Geometric Representation for Factoring (© 2013 kjro.se)

No matter how many different methods I have tried to work with this, I just keep ending right back where I started. My knowledge revolves more around computational complexity, combinatorics and optimization so Diophantine equations are interesting, but I’m not as deep into them as I would like to be.  I know there is a decent amount of work on Diophantine equations, if you have a good text to recommend that might gives some more ideas, let me know.

One other point to make is that for every k,l \in \mathbb{N}, l \neq (n+1)/2 there will be associated non-unique composite number (ie, it will work for other k', l'. Note, for any odd composite number, this representation will exist.

Playing around with this I’ve gotten some other ways of making sieves, but they don’t differ much from the primary techniques. There may be some interesting results this way regardless, possibly around distributions of certain types of numbers.

Next time, I will go through my notes where factoring is seen as solving for roots of an real equation, and how to create a pretty spiffy function that bounces off the x-axis for every integer.

KJR

9 thoughts on “Mathematical tomfoolery: factoring as a geometric problem

    • That’s an interesting idea. The structures around the solids could have some fun properties. Albeit, I’m not immediately sure the best solids to approach with.

      If only because going 3d would be interesting, I may play around with it.

  1. Indeed, factoring certainly is a Diophantine problem. What perhaps makes it so interesting is that even though Diophantine equations are so well-studied, there is no general approach to solving them. This is the result of Hilbert’s Tenth Problem. As such, there are many different paradigms for solving or finding information about them, and as far as I know, there is no single best reference. But Mordell’s Diophantine Equations and Henri Cohen’s Number Theory: Tools and Diophantine Equations are both well-known and respected by my peers (I’ve only looked at Cohen, and it seemed good, but I did not work through it so I cannot really say). Neither of these are elementary, but it seems you have a strong math background.

    I’d also like to say that the fundamental approach you recommend, i.e. writing pq = (l+k)(l-k), is the primary motivation for the Fermat factorization method (disclaimer, link to my own blog – there is also a follow-up on speeding Fermat factorization up).

    • I will pick those books up.

      Yeah, BMath Honours from UWaterloo in C&O and MSci in Mathematical Biology from Calgary.

      Would like to go into a PhD eventually, but cannot find a prof who is interested in the esoteric stuff that I love in computational complexity and biology.

    • Whoops – while my above comment waits for moderation, i see that I mangled my second html link. This is the actual link to my follow-up post on speeding Fermat factorization up. Sorry about that.

    • Quite possibly. I just find a different angle on the problem to be fascinating. For example, one of my other approaches uses a function where the only roots are the factors of n.

      Regardless, it doesn’t hurt to put it down.

  2. Joe says:

    The big stumbling block with this problem people found was that while you can greatly speed up factoring, it’s still a hard problem because of the insanely huge numbers involved. Indeed, 1024-bit RSA is considered obsolete. You’d probably love to look at the Prime95 or Mersenne websites. Especially concepts like the Chinese Remainder Theorem and field/FFT concepts.

    Keep in mind that the article was written in 2010, and do a search for “RSA crypto defiled again, with factoring of 768-bit keys”. Yes, the (non-spook) experts can factor a 231-digit number in a practical time.

  3. I think it is necessary to write down the solution of this equation:

    $(5z-4x)(5z-4y)=25xy$

    Solution has the form:

    $x=725p^2+770ps+125s^2$

    $y=125p^2+770ps+725s^2$

    $z=725p^2+1466ps+725s^2$

    Or.

    $x=-20ps-25s^2$

    $y=-25p^2-20ps$

    $z=9ps$

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