A further suggestion that P!=NP


There are a class of mathematical problems known as “P”: these can be solved in “polynomial time” or, to cut to the chase, they are problems for which we know how (algorithmically) to solve when we see them. A trivial example is -if you are given a number X, how do you calculate Y which is  X times 10. (If you don’t know the algorithm to multiply a base 10 number by 10 then stop reading this now!)

There are another class of problems – the “NP” (as in “Not P”) problems for which we know how to check if we have a correct solution to the problem, but not how to solve the problem itself. A typical example is producing the factors of a very large number created by multiplying two very large prime numbers together. If I gave you the factors you could probably verify that their product was the larger number, but if I gave you the larger number you might be here until the end of the universe trying to figure out what the factors were, as the only real way we know of (today) is to eliminate every prime number, one by one.

But, it may just be the case that “NP” problems are actually “P” problems after all, and it’s just we have yet to discover the algorithm to solve them. If we could show that NP=P in this way then we could do things like simply draw up train and class timetables instead of fiddling with expensive and approximate software tools to get these right.

But we’d also be able to crack internet encryption, which essentially relies on large numbers produced by two very large primes (public and private keys). These “one way functions” – i.e. bits of maths easy to do one way (multiply the two primes) but essentially impossible the other way – factor their product – are at the core of internet encryption.

Encryption and mathematics are deeply entwined and so communications intelligence agencies like the NSA in the United States and GCHQ in the UK are also centres of mathematical excellence – trying to break codes and, we must assume, test whether P=NP after all.

So this fascinating story about the state of encryption software in the US might suggest to us that the NSA have not been able to prove P=NP (most mathematicians think P!=NP but that is not proved either).

(The story essentially suggests that the NSA have paid to have a widely used form of internet encryption – Dual_EC_DRBG – operate like an Enigma Machine where the starting positions are always known. As with Enigma, once you had that, everything else would fall into place and what looks like a random sequence of letters is quickly converted to plain text.

Of course it could all be paranoid nonsense or even a cover to make us think that they haven’t cracked the P=NP problem (as, after all, you’d guard that secret with everything you’d got – except internet encryption!) – paying out a few million dollars to make someone think you had doctored one way functions because you could crack them no other way would be money very well spent!

The world’s fastest computers


Every six months or so a list of the world’s fastest computers is published in the “Top 500” list.

Except it is not. For surely the world’s fastest computers are in the hands of the NSA, GCHQ and whatever the French and Chinese equivalents are (I think we can probably discount the Russians for now)? At least I hope so – us taxpayers ought to be getting something in return for the money we are ploughing into these bodies.

The “revelation” that the NSA are seeking to build a quantum computer is most remarkable for the fact it suggests that have not already got one. Just as the problems the British authorities had, back in 2011, with rioters co-ordinating their actions through encrypted messages told us nobody at GCHQ had proved P=NP, what is most interesting about these stories is what is missing, not what is in there.

(Of course, there is another explanation on the riots: GCHQ have proved P=NP and are even now using this fact and the algorithm they have developed using it to crack everybody else’s codes and fundamentally a few wrecked city centres are less important than that. But I doubt this very much.)

%d bloggers like this: