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

2 things I’ve learned from having a newborn for a month.

So, William is now officially just over one month old. As a new father, I’m learning some very surprising and useful tools for dealing with him and maintaining sanity. Most of which revolving around that short period in the evening when either Suzanne or I want to get some rest. Overall, the kid seems to be healthy and happy, so I think the first month has been successful. He is starting to look at people more and respond to conversation which is really nice because before that he always seemed totally lost to everything.

I was thinking the best way to lay out this month is to put down the 2 main things I’ve learned to share with other possibly new fathers coming down the pipe so they don’t make the same mistakes. Pretty simple stuff that you don’t realize really matters until you need it.

#1 It’s not safe to go to sleep naked

While sleeping naked wasn’t a common thing for me, every once in a while I’d come out of a bath, be comfortable and just crash. I have discovered that this really isn’t wise once you have a kid kicking around, and not just for when they grow up. You may be needed at a moment’s notice to spring into action, and unless you have access to a self-dressing Iron Man suit, you are going to end up having to work (and run around your living quarters) in the buff. As a father, your duty is to take action when the mother is tired and exhausted and just needs a few more minutes rest before she has to breastfeed again. This means keeping the baby quiet while you address all of his needs.

Before you have a newborn, this isn’t entirely a problem. Once you get a moment to breathe, you can throw on some pants or a shirt and be off to work. However, you don’t get the luxury of taking your eye off a bawling newborn for that long. If the baby cries too much or too loudly, you will have failed at your primary task, ensuring mother gets a few more winks of sleep. If the baby is calm, but on a changing table, you really can’t take your eyes off of them for a moment. Thus, if you are naked when you start, it’s quite likely you’ll be naked while carrying a crying, wet, and possibly random-liquid spraying baby with you while trying to desperately calm him down.

All of which could’ve been avoided if you threw something comfortable on before you went to bed.

#2 At night, go pee before you change the baby

Do you know what almost always takes longer than you’d expect… changing a baby’s diaper. It’s not that it’s complicated. It’s actually one of the easier tasks I have to do day-to-day. However, there are always surprises.

Everyone knows about the sudden pee fountain, which is easy enough to avoid and usually just involves another diaper change. This, however, is the least of your concerns. The ones I’ve cataloged so far include:

  • the baby volcano, where just as you get a new diaper in place and ready to tie up, baby decides to take the longest and most bubbly poop ever. So named for the resemblance to the science volcano from when you are a kid and the fear you have that it will either burst or spill over the edges of the new diaper.
  • the poonami (I’ve stolen this from a friend), where baby suddenly decides to expel liquids from all orifices at the same time. Ensuring a fun and extensive clean up time as baby giggles at you.
  • the super-duper-pooper, baby poops just enough to ensure you need to change his diaper, waits for you to complete the change when, *Bblllrrprpr*, he poops just enough to require yet another change. Wash-Rinse-Repeat for about 3-5 runs.

Now, imagine having to pee really badly through all of this, and knowing you can’t actually go pee until the baby is properly dressed and back in the crib safely. As well, having the weird impetus to pee emphasized by the fact that baby has no problem at all peeing… everywhere.

I realize that both of these revolve around baby, nighttimes and bodily functions. However, for the first month, that’s really where 90% of your memorable interactions with baby come from. During the day, when you are sane, clothed, and awake, the interactions are fairly straightforward. Baby will eat, sleep and poop, almost like a cat. Your job is to clean up the poop and ensure he keeps on eating.

At night, unlike a cat, baby will continue these operations and still require you to be on the ball, being ready for this is key for any new father, and having read very very many father books I never saw these two lessons listed out.

They are important.

Trust me.

Enhanced by Zemanta

Sorry for the lack of updates

Writing
Writing (Photo credit: Wikipedia)

Mea culpa, mea culpa, mea culpa. Since my new baby boy has arrived I’ve had lot of interesting drafts, but not enough time to clean them up and get them live for you.  I am hoping in the next week once I’ve caught up on some of the major Panda Rose projects I’m elbow deep in, that I will be able to find an hour or two and get them out.

Lots of interesting topics to come though. For example:

  • “Hope is not Optimism”
  • The Boston bombing, panopticon, police and Reddit.
  • Reflections on 3d printing, and what needs to be done to break through that glass ceiling
  • The hidden propaganda of popular government programs (laws)
  • The false assumption of progress
  • Some interesting graphs and progress on the n = ab = (x-y)(x+y)
  • Some progress on what Average Mutual Information is, and why it may actually be a useful measure of ontology.
  • Liberalism and the Tower of Babel
  • “Business is relationships.”

As you can see, just because I’m not publishing, doesn’t mean there isn’t a lot coming down the pipeline. Hopefully I will be able to get some of the more timely ones out for everyone in the coming weeks.

Have fun,

Panda Waving
  KJR

Enhanced by Zemanta