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+(1^2)) = 6
p = 6 – 1 = 5
q = 6 + 1 = 7
Then confirm the results.. (5*7 == 35) and we’re done!
x = sqrt(77 + (1^2)) // is not an integer. Stop.
x = sqrt(77+(2^2)) = 9
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
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.
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.
Is it too much to ask for Halifax transit to enforce their own rules?
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.
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?
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.