Is your telephone number a prime number?

Artur Ekert gave a extremely entertaining talk. Bits of history about the quantum information community got mingled with digressions about prime numbers, and everybody was “hijacked” by Artur’s lecturing style. Even a bottle of cachaça was offered for those whose mobile phone number turned out to be a prime number! I’m not sure I can claim the prize, but my Dutch phone number was a prime. Since I no longer use this number I can write it here: 061048530. If you remove the initial 0, it’s a 8 digits prime number, as you can check here. When I came back to Brazil, when offered mobile numbers to choose from, I chosed a number that ended in 1, but it is not a prime… But let’s go to the lecture.

Quo Vadis quantum cryptography — Lecture I, Artur Ekert

Artur is worldwide known, among other things, for his 1991 paper on entanglement-based quantum key distribution. If I understood him right, after some initial excitement with the quantum cryptography subject he felt that things were going too “applied” for his taste. The recent years, however, saw a new burst of fundamental ideas with the development of device-independent protocols. I guess that is where the lectures are heading to, and maybe also the whole quantum cryptography community. As the title of Artur’s lecture imply, though, apparently we are no too sure about what surprises the field, and the lecture, still hold.

In any case, Artur started by explaining the one-time pad protocol. The also worldwide famous Alice and Bob made their first apparition in the school. Suppose that Alice wants to transmit a secret message m with size |m| to Bob. If they share a string k of the same size of the message and that have been drawn from the uniform distribution, what Alice can do is to send m\oplus k. Since the shared key is random, for any one trying to read the message it will appear as a random string. Bob, however, can decode the message by simply summing again the key as m\oplus k \oplus k = m. This protocol is information-theoretically perfectly secure, yet not feasible in practice. The problem, clearly, is with the sharing of the secret key! Note furthermore that the size of the key must be the same as the message, turning things quite complicated.

Artur gave then some insights on how public-key distribution works in the classical domain. The picture is based on a safe which contains two key-holes, one that can only lock and another that can only unlock. If Bob sends to Alice one of such boxes with a locking key, Alice can put her message in the box, lock it and send it back to Bob. Since Bob is the only one that has the unlocking key, he is the only one that can read the message.

In the real life however, both keys are mathematical objects and are somehow related to each other. Think for instance on the RSA algorithm. The key thing, if one cannot overuse this word, is that to discover the private key from the public key one has to solve some difficult problem, like factoring large numbers. Difficulty here is the sense of complexity classes, and Artur used this chance to give us a somewhat non-rigorous crash course on complexity classes.

You can probably see how the discussion about prime numbers came about, ending up with Artur claiming that among us at least 3 people would have prime numbers as phone numbers. This turned into a bet, and the currency in Paraty seems to be bottles of cachaça 😉

I’m really looking forward to Artur next lecture… and maybe to a bottle of cachaça!


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s