Enough said.

# XKCD nailed it.

# Factoring large semi-primes

tl;dr a friend of mine mentioned this problem over beers, and neglected to tell me that it’s considered impossible (thanks). Me being me, I gave it a shot, and appear to have devised a legitimate attack on large semi-prime that is not dependent on their size.

Long story short, it’s easy to multiply x * y, but harder to get x and y from back out of the answer. At it’s most basic level, 7 * 5 = 35. Conversely 35 = x * y, solve for y. There can only be one valid answer if both factors are primes, and when both factors are primes the product is called a ‘semiprime‘

It’s asymptotic complexity. In short, it sucks to brute force. It’s easy for a 2 digit number, not so much for a 200 digit number. That ‘s why no one uses 2 bit RSA keys. This mathematical asymmetry is the entire basis of RSA encryption.

Before we continue, let’s declare a few variables. *p* is the first prime, *q* is the second prime, *pq* is their product (and the semi-prime).

The most obvious speed-up is limiting the search space.

- The
*p*and*q*will never be even numbers. *p*will always be greater than the square root of*pq*, and*q*will always be smaller.

At this point, the search gets a bit smaller. But it’s still huge. Taking some time to refactor the formula (and I skipped a step or two, I’ve lost my original notes though will try to recreate them at some point)

*x = *sqrt(*pq+*(*n*^*2*))

*p = x – n*

*q = x + n *

We can simply increment *x* until *p***q* == *pq*.

A few examples;

x= sqrt(35+(^2)) = 61

p= 6 – 1 = 5

q= 6 + 1 = 7

Then confirm the results.. (5*7 == 35) and we’re done!

x= sqrt(77 + (^2)) // is not an integer. Stop.1

x= sqrt(77+(^2)) = 92

p= 9 – 2 = 7

q= 9 + 2 = 11

Then confirm the results.. (7*11 == 77) and we’re done!

We’re at this point effectively looping through *half of the difference* of the primes, which is a lot smaller space than *every number ever*. This algorithm **can factor a 50 digit prime in milliseconds on a netbook**. This algorithm is fastest when the numbers are closest together.

Since we know both *x* and *n* are integers, we can do the search the other way, as x changes slower than n, by reversing it we get a speedup.

We can rearrange this as

x = ceil(sqrt(pq))

n = sqrt(x^2 – pq)

n = sqrt(6^2 – pq)

n = sqrt(36-35)

n = sqrt(1)

n = 1, x = 6.p = 6+/- 1 = 5, 7.

Obviously the bigger the numbers are, the greater the difference between them. Ironically, it’s recommended to use values of p and q which are relatively close together. ~~Thus this may be a valid attack against an RSA key~~

It’s non-deterministic, and can be parallelized (give each machine a 100,000,000,000,000,000 digit range to search

The only further speedup I see is if there’s a way to solve for the next integer value of *n.* The limiting factor here is that it’s effectively approaching a linear search as x approaches infinity. It’s extremely fast until the slope straightens out.

I’ve yet to come up with something so throwing this algorithm out there to see if anyone else can take it that last step.

**UPDATE:** Looking into it more, it’s a massive speedup in a small field, but not a large field, as it approaches a linear search of the difference between primes as x approaches infinity. This is fine for a 50 digit semiprime, but not a 200.

# Redbull doesn’t give you wings

Whodathunkit?

http://energydrinksettlement.com/claim

# Splicing Cat5e

Wanted to move my ~~modem~~ router to another room. Cat5 already running there, and the connection is only 50/30 anyways, so just spliced into it.

Now, generally that’s done with couplers and terminated ends. I didn’t happen to have either on hand so used duct tape and crossed fingers.

Works for now, I’ll do it right ~~some day ~~when it stops working.

# Reserves

Just seriously considered joining the reserves for all of 0.3 seconds.

Then I remembered we’re fighting a Holy ~~War~~ Armed Conflict.

# Lego is releasing a minifig scale Firespray

Of course, it’s *Slave One* not the *Andrasta*, but that would be asking a lot.

Hopefully they’ll release an alternate along with the YT-2000 *Otana*.

And yes. I’m bitter that there hasn’t been an X-Wing alliance remake, can you tell?

# Strollers in the wheelchair spots

Why is it that all of a sudden bus drivers allow people to fold up the wheelchair seats for massive strollers?

From the globe and mail:

Metro Transit guidelines allow “smaller” strollers, defined as those up to 105 by 56 centimetres, and asks that babies be carried while on buses. Drivers have explicit authority to prohibit larger strollers.

The rules clearly say that a stroller has to be folded up too. And I can’t see the Escalade of strollers that just got on being all that safe in a collision. Wheelchairs are tied down.

The drivers don’t dare say anything in case the parents file a lawsuit or call the police.

Is it too much to ask for Halifax transit to enforce their own rules?

# Stupid patents

Apparently Microsoft has patents on “showing multiple windows in a web browser”

That is insane. But wait, there’s more!

They make a BILLION DOLLARS on royalties from Samsung android devices.

# UX theory

I was told the other day that top 20 lists, which have twenty separate page loads, are “great UX”

You Keep Using That Word, I Do Not Think It Means What You Think It Means –

Inigo Montoya

# Logical fallacies 101

Why aren’t logical fallacies a required subject in school?

“You can’t prove you didn’t do something so you must have”

Ran into that one today. Not only is it impossible to prove I didn’t do X, its impossible to do X, and someone is going around saying I did X.

My head hurts.