Mathematical tomfoolery: factoring as a geometric problem

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)

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

Baby Family Father Father Day Gift Happiness Home William

My first Father’s Day weekend.

Small hand – Big hand (If this image doesn’t show up, blame Instagram)

Father’s Day weekend has come and passed; almost perfectly timed with William becoming a social creature. I will admit that before he became social, it was a bit odd taking care of him. He was pretty much a cat that can’t walk around – ie. eat, sleep, poop, repeat. My job was to clean up the poop.

I could try/pretend to play with him and such, but he would barely respond in any way that could be considered social. So, those moments were more me playing with myself.

A little while ago (couple of weeks I think), he started to smile back at mommy and me. the first time that happened, it was pretty amazing. Whether it was an instinctual or automatic response on his part, it still felt like he was finally showing how much he cared and appreciated the efforts we were putting into making him happy and comfortable. He ceased being a cat, and started being more human.

This week, almost as a father’s day gift, he started to talk back in response to me, hold my hand and pull me near when he was lonely, and the very best, squeeze when I held him. I would bet that many people with children would understand this. There is no greater feeling. I wish I could explain it fully.

I can only explain it from my Catholic faith – it feels like pure unadulterated love. The type of love that is described in catechism to young people, who are probably too inexperienced to really understand it. He is no longer needing you there, he is wanting you there. He doesn’t even really know why.

This continued to peak during this Father’s Day weekend; specifically just after Suzanne gave me William’s gift, a cute t-shirt that said “daddy is my hero.” Now, you must admit that was more of a gift for himself, but I can excuse it since he’s still young and learning things like “gift-giving.” I smiled, give him a peck on the forehead and moved on with my day.

Then he started to cry…

and cry…

A strange new cry, almost inconsolable. He wasn’t hungry, didn’t have a wet diaper, and wasn’t dealing with the common gas pain; he didn’t want his swing, or his playmat, even a bath didn’t help.

No, he was just crying… a lot.

“I want daddy hugs.” (Again, if no show, blame instagram)

Then I had a strange idea – I sat down on the couch and held him in my arms without walking around or bouncing him. Almost immediately, he went quiet and, even stranger, started to squeeze my sides and closed his eyes. This may seem boring and common, but this was something he had never done before.

In a short period of time, he seemed to have fallen asleep, and I thought, “great! He’s asleep, I can put him down and help mommy with cleaning the house.”

Nope. The moment I put him aside, he immediately returned to inconsolable unhappiness. so, I would pick him up again, he would squeeze and then fall asleep.

After a half-hour or so of this (passed by playing Candy Crush and reading Zite on my iPhone.), I wanted to actually get some work done. So, I asked mommy to come and take him, foolishly thinking it was just the warmth of my body calming him down.

Nope.

Inconsolable sadness.

He clearly wanted his daddy for Father’s Day.

This could all be coincidence and just lucky timing, but I wonder, deep down, if perhaps he just knew somehow. It was Daddy’s Day, Daddy is his hero, so he wanted to spend as much time with me as possible.

And to be honest, I enjoyed every moment of it.

KJR

big brother boston bombings Business conservative government information liberal power PRISM project privacy reddit

We live in a panopticon, congrats.

Plan of the Panopticon (Photo credit: Wikipedia)

A panopticon is a building designed in the late 18th century by Jeremy Bentham. Designed to be a prison, it allowed a single watchman to observe all inmates of an institution without them being able to tell whether or not they are being watched. It was a method of control, it was a method to ensure compliance, it was a method of punishment.

It was not designed to be something nice for the prisoners, only useful for the watchman who’s job was made significantly easier at keeping everyone in line.

In the last decade, we have built a panopticon in the western society – This is the largest social experiment ever.

The public panopticon

With the Boston Bombing, it made it crystal clear that we now live in a world where there are so many digital photos and videos that given any public event, anyone can watch anyone else with very little effort. With inventions coming down the pipeline like Google Glass, this will simply become that much more pervasive.

Reddit went crazy with amateur detective work during the early days, listing over a dozen different suspects based simply on their dress (The blue robed man), their backpack (Some runner with a similar backpack), the fact they went missing suddenly a few months back (A poor guy with some mental issues who disappeared from his school). All from the multitude of pictures and videos they were able to collect of the event.

All of whom ended up being completely innocent people just standing around watching a marathon. Thank god we don’t have lynch mobs anymore, right? Thank God we have a informed and careful media that doesn’t simply publish unsubstantiated photos of innocent men based on amateur detective work, right?

Crowdsourcing can be a good thing to raise money for good causes, to create new business opportunities, and to build new tools that are freely available for all to use.

However, crowdsourced panopticons are an immensely dangerous tool, and we are exposed to them now everyday. Our privacy disappeared with Twitter, Instagram and Facebook. We can try to take it back, but when a significant portion of your social life and social circle communicates using those tools. There really isn’t any escape without social isolation.

We live in a public panopticon of our creation.

This isn’t a question of privacy anymore, this is a question of actual freedom. There are regularly stories of people losing jobs because of a Twitter post that wasn’t politically correct enough, or of a photo that got posted that shouldn’t have. Individuals are told to be very careful at parties with alcohol, lest one of their friends get a photo of them intoxicated and tag them in it.

We lose our freedom because we are made to be afraid to say the truth, afraid to say our beliefs, afraid to say anything that deviates from popular opinion. Many reasonable voices are silenced, afraid that if they err in what they say, or if they change their mind a few years later they will be punished for their past sins.

We cannot say anything if it isn’t politically correct or “nice”.

The only voices that get heard are the anonymous ones, the ones who already have power, or the loud-mouths who don’t care to begin with. Actual dialogue is reduced to fearful whispers, and arrogant rants. Since we live in a panopticon, many live with an overwhelming fear that we aren’t doing enough, aren’t doing it right, that our mistakes will chase us for the rest of our lives.

We fear that people are watching our every move, our diets, our lives.

We fear the watchmen, but the watchmen are ourselves.

The private panopticon

Joseph McCarthy — “I love Facebook” (Photo credit: History In An Hour)

Today, an oppressive government has no need for a Stazi, it is trivial to see who everyone else relates to simply through their followers and friends on Twitter and Facebook. Joseph McCarthy would have a field day. “Are you now, or have you ever been a communist?” is answered by a quick glance at our Twitter or Facebook timeline.

Even if we didn’t post the items ourselves, it is not hard to data mine and put 2 and 2 together to figure out the answer to that question. This is the entire essence of big data, believed to be used for marketing purposes, but in recent days shown to be used for far more than that.

The NSA and CIA spy on Americans (and non-Americans). This is not surprise, and is a bit of a tautology. However, the extent of the spying still was restricted by the capacity of the technology and, hopefully, the limitations of the law.

The PRISM program disclosure demonstrated that now there is no limitation. They have access to the panopticon we have created to combine with their own already extensive structure.

It is clear that the PRISM program shocked all of us, and seeing it so clearly laid out in those slides demonstrates how complete and penetrating it is in our society. Yet, this is a panopticon our own creation. We built those walls that we lie in, we placed the watchman there ourselves out of fear that one of our our fellow inmates may try to hurt us. This should not be a surprise to anyone.

Now our leaders assure us that this is all perfectly legal, we shouldn’t mind the fact that they can listen into our phone conversations, view our private emails and facebook discussions, that they can watch us at any time with the thinnest of motives. Don’t worry, they won’t abuse it… really.

It’s for our safety you see. It’s to protect us from ourselves.

“If you have nothing to hide, then why worry about it?”

We are all sinners, we all make mistakes. We all have something to hide between us and God. If the watchman can see everything we do, he has the power to make us doing anything he wants. If we disagree with what the watchman feels is nice or right, then we could be in a lot of trouble.

Power has always attracted abuse, and absolute information will bring absolute power to him who controls it the most.

“Power tends to corrupt, and absolute power corrupts absolutely. Great men are almost always bad men.”

Lord Acton in a letter to Bishop Mandell Creighton, 1887

Are we so dull that we have forgotten this? Are we so satiated by our consumer culture that we are ok with giving this power away without a fight?

Information is power, anyone who has studied financial mathematics knows this. Arbitrage and acquisition of money without creation of value is best achieved by a imbalance in information.

The Republicans will do nothing about this, the Democrats will do nothing about this, nor will the Liberals, Conservatives, NDP, Labour Party, or any other party running for office. They want to control the levers of power, not break apart this massive machine. That information is the potential to rule with almost absolute power, why would they ever consider getting rid of it?

What can we do about it?

I don’t know. I know protests are ineffective, as will voting for any politician who is already in the system, and the media doesn’t seem to be having much effect.

Perhaps that’s what many, including myself, missed in Orwell’s 1984. A absolute totalitarian society wouldn’t arise through a violent takeover, but through people simply giving up their privacy for convenience and baubles.

Big brother is watching and we all seem willing to let him do so.