So I’ve always been fascinated by the problem taking a number 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 and are prime numbers, and let . 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,

It is true that

where

Thus, given an where we know odd, then we can easily see that , and

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

For the more geometrically minded, this means factoring is solving the following diagram for .

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 , there will be associated non-unique composite number (ie, it will work for other . 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