Tag Archives: Number theory

Primes from a Different World

Every textbook on number theory will begin with a treatise on prime numbers; every treatise on prime numbers will begin by emphasising their importance as building blocks or atoms of our number system: every integer can be expressed as a product of prime numbers in one way and one way only. Six is two times three and there is no other way to decompose it.1 Euclid proved this over two thousand years ago and it is so fundamental (hence the name fundamental theorem of arithmetic) to our thinking about numbers that we take it for granted. It is not!

There are numbers that behave very much like the integers but have a different structure. One rather simple example are the Gaussian integers (usually denoted \mathbb Z[i]) which look just like complex numbers z=x+iy, except that x and y are restricted to integer values. They live in the complex plane, but exclusively on a discrete grid amongst their continuous cousins.

Gaussian_integer_lattice.svg Continue reading Primes from a Different World

  1. Yes, you can write 12 as 3*4 or 2*6, but you can continue either way and eventually reach the unambiguous 2*2*3. 

A Toy Keyless Encryption Protocol

Cryptography is a natural application of number theory and so I'd like to write down a few thoughts about it in this blog. (The fact that there are real world applications to number theory deserves some appreciation in itself, but it would throw us too much off track here.) One particularly nice feature of cryptography is the ability to explain its inner workings with real world analogies about security.

For instance, one way two parties (who we, by convention, call Alice and Bob) could hide their secrete communication is if Alice writes a letter, puts it in a box, and locks it with a padlock for which both she and Bob have a key, but no one else. Then Alice can send this box safely through any public means as anyone who intercepts it will not be able to open the box, rendering it useless to them. This is the principle behind symmetric cryptography. The obvious problem is that Alice and Bob will only be able to communicate if they managed to obtain identical keys beforehand.

Alternatively, Bob could distribute padlocks for which only he possesses the key to anyone who's interested. Now Alice can obtain such a padlock, use it to close the box with her letter and send it off to Bob. She won't be able to open the box, but neither will anybody else -- except Bob. It sounds tedious to ship padlocks for every single communication, but the advantage is that there's no need whatsoever for Bob to restrict distribution to trusted parties, making it possible for anyone to send him messages securely. This is the basis of public key cryptography (a field which is extremely number theory heavy -- a course about it will feature extensively theorems on primes, groups, elliptic curves, lattices, and many more really abstract concepts).

But there is yet another way parties could communicate securely. Let's imagine Alice uses a lock for which only she has a key. She ships this of to Bob who cannot unlock it himself -- instead, he'll add another padlock himself and sends everything back to Alice. She couldn't open it herself anymore, but she can remove her padlock and still send it off to Bob once more knowing no one except Bob will be able to open her secret. Finally, Bob opens his lock and can read Alice's message. No need to meet up and share keys, no shipping padlocks. Continue reading A Toy Keyless Encryption Protocol

If One at a Time is too Difficult, Try All at Once!

In the past months, I spent as much time as I had on taking online courses at Coursera. One particularly interesting course, both from a mathematical and computational point of view, is Analytic Combinatorics which applies combinatorics (i.e., the art of counting) to the analysis of algorithms by finding formulae, exact or asymptotic, for their running time.

It is notoriously difficult to find exact formulae for general combinatorial constructs. Typically, we want to know how many objects, e.g., trees, permutations, sequences, with certain properties there are of a given size. Famously, the number of binary trees (and about a million other constructions) is governed by the Catalan numbers

C_n = \frac{1}{n+1}{2n\choose n}.

Continue reading If One at a Time is too Difficult, Try All at Once!