E-mails and comments welcome from teachers and learners of all ages.
April 25, 2003
Prime bear

Dave Barry (archiving mess  scroll down to Wed April 23) calls this his "educational site of the year". Yes it's Alkulukuja Paskova Karhu, the Prime Number Shitting Bear.

I actually learned quite a lot about Prime Numbers from this eccentric animal, like how around 1,000 they are a lot more frequent than I had supposed, nearly as close together as they start out being.

I don't have to have it explained why mathematicians find Prime Numbers fascinating, because they find anything mathematical fascinating by definition, but do Prime Numbers have any uses other than as something for joke bears on joke websites to emit from their recta? I've heard they're used for encoding things, or maybe for making it impossible to decode things. How does that work?

And do primes have other uses? Surely they must. Commenters who know maths? Here's your chance to broaden the minds of all the maths-phobic humanities snobs who flock here by the thousand.

And linguists! What language is "Alkulukuja Paskova Karhu", and what does it mean? I'm guessing it's Russian, and it's the bear's name, but what do I know?

Indeed, they have a number of uses in cryptography. I'll describe the simplest, called the RSA algorithm (for Rivest, Shamir and Adleman). Say we have two large prime numbers (in the several hundred digit range) p and q, and we multiply these two numbers together to get n=p*q. We also pick out a number k, called the public code. If we want to encode a number m, smaller than n (and any message can be broken up into blocks of this size), then we compute the number m to the power k, dividing at each stage in the computation by n, and taking the remainder. This is called modular arithmetic--it's like the arithmetic of a clock, where 23 equals 11, but this is modulo n instead of 12. Anyway, this computation is fairly easy to perform, and you can give away the number k to anyone you want, but only the knower of the prime factors can easily reverse it. The inverse function depends on the period of the exponentiation function mod n, which depends heavily on the prime factorization of n. If you know it, you can easily compute the period, and hence reverse the encoding. If not, you can't do too much.

Finding such enormous prime numbers (in hundreds of digits range) is possible because of an amazing algorithm called the Miller-Rabin pseudo-primality test. It gives the answer "Yes, this number is prime" to an arbitrarily high level of certainty, and if it ever returns "this number is not prime", then the number is definitely not prime (though you don't know a factor of it). An amazing cousin of this algorithm was published last July (on the web! it still hasn't appeared in print) which definitely returns "yes, this number is definitely prime" or "this number is definitely not prime" in an amount of time, which increases relatively slowly to the size of the input. This amazing bit of technical mathematics is without application (yet), contrary to hype you might see in the press.

As for other uses of prime numbers, I know they're used in other kinds of cryptosystems, but aside from that, I'm largely ignorant. I understand that certain kinds of problems involving the distribution of zeros of Riemann's zeta function appeared in quantum mechanics, and the zeros sort of "encode" the distribution of the primes. David Broadhurst (a physicist and amateur number theorist) did some work along these lines a few years ago, though I only cared about the mathematical consequences of his work at the time. Perhaps Michael knows of other applications?

P.S. If something in the above was unclear, please ask questions. Number theory (and especially the theory of the primes) was my first love in mathematics, so I love seeing nonmathematicians interested in it.

Comment by: Lucas Wiman on April 25, 2003 05:09 AM

Re: your comment on the distribution near 1000. The distribution of prime numbers is a fascinating subject, which was really begun by Carl Gauss. He looked at tables of the first several thousand primes and noticed a regularity: say you want to know how many primes there are up to n. Then this is close to n divided by the natural logarithm of n, and it gets closer as n increases. Now as n gets bigger, this predicts that heuristically, the probability that a random number near n is prime is about 1/log(n), where this is the natural logarithm. Around 1000, this is about 1/7, so approximately one out of every seven numers near 1000 is prime ("around" is fairly vague, hence this is solely heuristic). The prime number theorem was first proved around 100 years after it was first conjectured by Gauss, in the 1890's by a couple of French number theorists. Their proofs used complex analysis in a really clever way, showing the unity of disparate fields of mathematics.

The distance between primes can be arbitrarily long (easy to prove), and it seems it can be distance 2 infinitely often. This latter part is called the twin prime conjecture, and it remains unsolved. Interestingly, we can know a number of things about the distribution of twin primes, without even knowing whether there are infinitely many of them. The mind boggles.

Comment by: Lucas Wiman on April 25, 2003 05:32 AM

I'll shut up now. Once you get me started on prime numbers, I just can't stop.

Comment by: Lucas Wiman on April 25, 2003 05:33 AM

Ah yes, but if quantum computers ever develop beyond the abacus level, then prime number cryptography will be dead as a dodo!

Julius

Comment by: julius on April 25, 2003 10:13 AM

I think the thing that originally interested me about primes (I'm a non-mathematician) is the proof quoted by Euclid twenty-odd centuries ago, that there are infinitely many of them. They intrigued the Greeks because of their awkwardness, not being divisible into smaller numbers being the obvious oddity.

Weird as it now sounds, a major group in the ancient world was the Pythagoreans, a group who believed numbers have mystical significance and all the world is composed of number. In a sense, Plato, and all of the Western world since, has been a kind of continuation of the Pythagorean religion (yes, it was really a religion or cult).

If you're religious about numbers, you obviously enjoy dividing, multiplying, finding patterns (like noting that certain numbers form squares or triangles if laid out like marbles). You would like all of nature to reveal patterns that fit with this sacred vision of yours (and much of it does, from seashells to falling arrows). You find the sheer cussedness of primes a fly in the ointment, and as a matter of worship/magic, you study them deeply.

Numbers like 17 or 59 or 61 spoil a simple attempt to fit numbers into neat sets of grids and patterns, but if there were only a limited number of such numbers, some Pythagorean order would be restored, and you would be able to see them as a limited set of building blocks with which the infinite palace of number is constructed (for all numbers which are NOT primes {'composites'} are made by multiplying primes together, of course). There might be, for example, exactly three gazillion prime numbers and no more.

If there were three gazillion primes, and you multiplied them all together to get a jolly big number we can call ZOB, this is clearly a composite (because it divides by all those primes we used - in fact all the primes you reckon there are in the world). But if we look at the number one bigger than ZOB (which is ZOB+1) we realise something a bit disquieting.

Either ZOB+1 is a new prime, or it is a composite divided by primes. But if it is a composite divided by primes, none of those primes can have been in our original three-gazillion-long list, because all THOSE primes divide ZOB, and so cannot divide ZOB+1 without leaving a remainder of one.

Therefore both ways there is a three-gazillion-and-oneth prime - either ZOB+1, or a divisor of ZOB+1 not in our original list.

Therefore (since you can repeat this process as often as you like) there are infinitely many primes.

That is the proof quoted by Euclid twenty-odd centuries ago.

I think the thing that really intrigues most mathematicians about number theory (in which the distinction into prime and composite is a pretty central topic) is that there are still big unsolved problems which are deceptively easy to quote, but fiendishly hard to prove or disprove.

For example:

1. Are there infinitely many pairs of "twin primes" (like 17,19.... 29,31.... 59,61....), or is there a biggest pair?

2. Are all even numbers the sum of two odd primes (40=17+23, 60=17+43, 62=19+43...) or not?

...and other open number-theory problems which may not seem prime-centred may yet involve primes, such as...

3. Are 8 and 9 the only two consecutive powers?

-

Comment by: mark on April 25, 2003 06:51 PM

Mark: I disagree with you about the motivation. Mathematicians generally aren't interested in a problem "because it's hard," as a 300 year old unsolved problem usually is. It's rather because they find the problem or topic itself interesting. You'll note that it was the proof of the infinitude of the primes which first got you interested in them--not the fact that there are a number of hard problems which haven't been solved about them. It's the same thing with mathematicians. BTW, (3) (Catalan's conjecture) was solved last year by a brilliant mathematician named Preda Mihailescu.

Julius: Maybe. Certainly RSA will be dead due to Schurr's algorithm, but there are other methods of encrypting things (like elliptic curves), which also involve prime numbers but don't depend on the hardness of factoring. I don't know the extent to which these can be broken by quantum computing methods. They're in a different class of algorithms based on something called the discrete logarithm problem. To the best of my knowledge (and I don't know much here), there is no quantum algorithm for solving the discrete log problem, so some classical cryptographic algorithms might survive. Or maybe not. There is apparently a field called "quantum cryptography," which is waiting in the wings for such a day.

Remember, RSA was developed in the 1970's and still has yet to be really broken (though there are some interesting indirect lines of attack on it). I'd say it's done its job.

Comment by: Lucas Wiman on April 25, 2003 07:43 PM

Well, I shouldn't presume on what interests mathematicians, no! I guess I was trying to suggest what might be interesting about something to arts people (Brian's challenge) until now convinced that thing isn't interesting.....

Catalan is solved? I read about the claim someone had cracked it, but I didn't realise it was agreed and settled. So the answer is yes? 8 and 9 _are_ the only consecutive powers?

Comment by: mark on April 26, 2003 03:08 PM

Mathemticians are often interested in particular problems not so much because they are hard but because they are beautiful. Beautiful in mathematical terms tends to mean "elegant" in some way. Either the theorem you are trying to prove is extremely simple and elegant, or the solution is simple and elegant, or both.

Problems that are merely "hard" tend to be extremely inelegant in terms of both the problem (or theorem) itself and the solution (or proof). These are typically of less interest to a mathematician, but they can certainly be of practical use.

Comment by: Michael Jennings on April 26, 2003 10:08 PM

Lucas

I suppose the point is that there is no comprehensive theory as to what sort of problems might be solved by quantum computation. Accordingly, if quantum computation ever got to the multi-q bit stage, no user of prime number cryptography could ever be sure that his communications were safe unless he could be satisfied that all quantum computation algorithms were in the public domain (as opposed to being secret).

Of course in practical terms the issue is irrelevant until such time as quantum cryptography becomes practical for long distance communication (which is highly problematic for inhabitants of Earth as opposed to the moon or space!). Until that time, prime number cryptography will still be the best game in town

Julius

Comment by: julius on April 30, 2003 08:15 AM

The same problem pops up now. With most cryptographic algorithms, it is not known how efficiently they can be cracked. It's conceivable that the National Security Agency can read all encrypted communications on the internet if they want to. This isn't a serious problem for "prime number cryptography," whatever that is--people wishing to get electronic privacy even now have to take some of its claims on faith. Faith that's been justified by only by the failure of the best mathematicians and computer scientists to break the algorithms, that is.

Comment by: Lucas Wiman on April 30, 2003 05:18 PM

The language in question is Finnish, which is quite logical for a site situated in Finland (.fi).

"Alkulukuja paskova karhu" means "Prime number shitting bear". Nothing more :)

Comment by: Antti Rasinen on November 13, 2003 07:17 PM •