Cryptography, Part 1

One of the most important methods of security are cryptosystems and their application. They are the basis for security. But in the past they have been broken notably in times of war, when necessity was at its most dire. For each post in this series, I will concentrate a bit on history and also a bit on the systems used in the modern day.

How They Work

The most obvious form of cryptography is simply the encryption of a message by a sender, sending the message in its encrypted form, and the subsequent decryption of that message by the receiver. In its original form, the message is called plaintext and the encrypted form of the message is called ciphertext. This kind of encryption has been used for thousands of years, though the methods of encryption have been getting better and better.

Letter Substitution Ciphers

Early forms of encryption were simple letter-substitution ciphers. The Caesar cipher was quite simple, just treat the letters of the alphabet as though they were a circular group and rotate the wheel. If we rotate by one, then TEMPUS FUGIT becomes UFNQVT GVHJS. This appears to be quite unreadable at first glance. But once you know the method, there are only 25 possibilities to try. Well, there should be 26, but that would include the case where the wheel was not turned. In this case the ciphertext is exactly the same as the plaintext: and so we ignore it.

A graphical example of letter substitution is Polybius' square. Here, a letter is substituted by two numerical digits, a row and a column. This makes TEMPUS FUGIT into 44 15 32 35 45 43 21 45 22 24 44. Note that the blank, or word separator, is not encoded. Yet this substitution cipher is really just an early attempt at making an ASCII representation of the characters.

If you can't encode a blank, the phrase NOW IN can be decoded as NO WIN. This is a potential misread. So the better ciphers allow for more than 25 letters, as we will see. Well, the very fact that I and J share a square seems to imply yet another kind of ambiguity would arise from the use of this cipher.

Nonetheless, letter substitution ciphers fall prey to cryptanalysis, the science of breaking a code. To break the code, all you need is a long message. The letters of a message have a very likely probability distribution: the Zipf distribution for English. So we can use frequency analysis to determine likely decodings and pretty soon we have cracked the code.

How does this work? First off, we analyze the frequency of occurrence of the ciphertext letters. Then we match that up to the frequency distribution of typical plaintext. This will give us a few likely substitutions to try.

Well, actually one more thing might be needed in practice: a list of letter pairs. Some letter pairs will be commonly-occurring and others will not occur at all. We can use this to automatically determine whether a prospective substitution is valid.

So, you see, a simple letter substitution cipher is quite insecure.

So it wasn't very long in the scheme of things that this cipher was improved on. As it turns out, simply scrambling the letters in the Polybius square is not enough to make it more difficult. This just turns it into another letter-substitution cipher.

Codes During World War I

So, what can be done to make it harder to crack? During WW I, the Germans fixed the Polybius square in two ways. First, they used a scrambled alphabet. Also they used ADFGX as the row and column numbers instead of 12345. This really only made it a bit more visually confusing, since it is still a substitution cipher.

Here you see the result of modifying the Polybius square, using letters for the row and column, and scrambling the alphabet. This is a permutation. Each message could change the code book by using a different scramble. But there was more to the key than this, as you will see.

The next step is to substitute for the letters of the message, in this case MOVE GUNS WEST is converted to AA DX XF AX XG GD GX DA FA AX DA FG.

Then we lay the encoded result into the same 5X5. Note that an X is added at the end. If the message is more than twelve letters, we do this potentially multiple times, into multiple 5X5 arrays. It is important to pad the end of the message with random text (not just X's), or it may be easier to analyze!

Then we put a 5-letter word at the top, this is the next part of the key. And this is what makes the cipher so interesting. It creates a second permutation, on the columns of the text. What we do is to sort the letters of the word, and move the appropriate columns in the array as the letters move. So this means your word can't contain the same letter twice, like TWEET, nor can it already be sorted, like ABCDE.

Once we sort the columns, we get a modified array of text. The last thing to do is to read it out in columns to produce the ciphertext.

Although this method is better than simple substitution, it is vulnerable in several ways. First, there are only 120 (5 factorial) possible sorting orders (permutations) for 5 letters. If we try them all, then there will be one ordering that gives a better frequency distribution than all the others. Even if this is not so, you can try all the orderings with likely frequency distributions, and break them using known substitution cipher attack schemes. A poor fellow named Lieutenant Georges Painvin did this by hand in 1918 and successfully broke the German code (even after they had added another row and column to their array!). It nearly drove him crazy too.

Here is the cipher text for the original message. The reason it is longer is that the result is essentially in base 5, which takes roughly twice the space in symbols vs. base 26.

What the Germans wanted was a system where they could freely transmit the message in the clear (in ciphertext form) but not have it decoded by an interloper, in their case the French. To make this work, the sender and receiver both must know the same key. This is called a shared secret in cryptography. A system where one key is used to both encrypt and decrypt the message is called a symmetric-key cryptosystem.

The advent of computers really did change cryptography. But it also simultaneously changed cryptanalysis. This is where cooler, and more mathematically-oriented, heads prevailed and systems were developed that were extremely hard to crack, even using modern computers.

Public-Key Cryptography

A fellow named William Stanley Jevons figured out that one-way functions could be applied to cryptography in 1874. This was exploited by Rivest, Shamir, and Adelman at MIT in 1977 to create the RSA algorithm.

The basic idea is that there are two keys. One, the public key, is used to encrypt the plaintext, and another, the private key, is used to decrypt it. The keys are related mathematically, but computationally it is very difficult to extract the private key from the public key.

The technique for relating the public and private key pair in RSA is factorization. It's really quite clever. The public key is the product of two large (and I mean large) prime numbers. The private key is one of the prime numbers. What makes it work is this: it is relatively easy to determine if a large number is a prime. However, when a number is not a prime, it is very hard to factor it into a product of primes.

There are many wrinkles to public-key cryptography. For instance, the protocol for key revocation or replacement is one. Timestamps can be added for additional limits on the spread and validity of the privilege of decoding.

Authentication

The main reason for the private key is, of course, the authentication of the intended receiver. But can an interloper do something to compromise the message? Absolutely. Modifying the ciphertext when it is en route from the sender to the receiver is one way to compromise the message. This gives rise to authentication schemes.

When it comes to security, it is important to have three bits of knowledge: The first is that the message is being received by its intended recipient. If you are sending a message an ally, you would like to prevent your enemy from getting it. The second is to verify that the message did, in fact, come from the origin that is advertised for the message. If your enemy sends you a message that says it comes from your friend, this can be used to deceive you. The third is to know who had the message along the way. This is akin to the chain of custody in forensics. The point is this: can you trust the message?

We now use digital signatures to authenticate messages. More on this in a future installment.

How Does It Work, Part 1

Analytic geometry is one of the most useful kinds of mathematics I have ever learned. Painter was built on it. But the average person has little idea what makes it tick, much less what makes it relevant. This post will simplify two-dimensional analytic geometry and present it so anybody can understand it. I'll build you up from understanding points on the plane to segments and vectors. And then to angles, directions, orientation, area, really you name it (if it has to do with analytic geometry) and I can help you understand it.

The Plane, the Plane!

Pixels and points are two ways of looking at the plane. But both of them involve a two-dimensional address system, and the two dimensions are usually called X and Y, but sometimes also columns and rows.

We see here a right-handed coordinate system. On the compass, the X-axis points east and the Y-axis points north. In the center is the origin, the point where X and Y are both zero. We like to write a coordinate as an ordered pair, in this case (0, 0). The axes also split the plane into four quadrants (shown in color and with their conventional Roman numerals).

If you are working in columns and rows instead of X and Y, then you are actually using a left-handed coordinate system, because larger rows are below the smaller ones, and so the direction of increasing rows points south. Pixels in an image are usually laid out in rows and columns.

A coordinate system is the basis for all analytic geometry. A point is an infinitely small location in the plane. A pixel is really a small rectangle covering a (usually square) area in the plane. The center of the pixel is a point.

Vegments and Sectors

Wait, I meant segments and vectors (I'm just trying to confuse you with doubletalk, hee hee)! Join two points with a small straight line and you get a segment. If you join two points in the same way, but the join actually has a direction, then you have a vector. Segments and vectors may be measured and quantified in different ways. And each has their own use.

Here I show a segment from point P1 (X1, Y1) to P2 (X2, Y2). A segment is rooted (meaning it has a real position on the plane) because both endpoints have locations.

Segments may be chained end-to-end to create polygons. Most commonly, a polygon is closed, in which case it has an inside and an outside. You can compute a closed polygon's area also. More (much more!) on this later.

Here is a vector from point P3 (X3, Y3) to point P4 (X4, Y4). But a vector, which we have conveniently defined to be the straight path between these two endpoints is really not rooted and consists of only an X and a Y delta. A vector is pretty much the same no matter where you put it.

A vector's measure starts by computing the X and Y deltas that make it up. Once you perform the subtraction, any notion of being rooted in the plane goes away. Why? This is intuitively true because you subtract away the start point of the vector, removing its home base.

Length and Stuff (No, It Isn't Spelled Lenght! Grrr!)

Simple subtraction creates the vector, as you can see. This is why a vector is oriented. A vector from P3 to P4 is quite different from the vector from P4 to P3. In fact, it is the negative of it. Or inverse.

Its length may be easily calculated using Pythagoras' rule by making the segment the hypotenuse of a right triangle (you probably wondered when that rule was going to be useful to you in everyday life, right? Well, just wait until you get to trigonometry!).


So here is the easy way to compute the length of a segment. You move the "right angle" of the imaginary right triangle (kind of shown shaded in a very light peach color) directly to the origin. This translation is effectively performing a subtraction, in this case, of the lesser of the two X's, which happens to be X4, from the two points, and also a subtraction of the lesser of the two Y's, Y3, from the two points. Anyway, the base and height of the right triangle are now known, so we may compute its hypotenuse length using Pythagoras' rule.

Note that, when you square them, the deltas that make up a vector can be either positive or negative. This is because their signs get lost when you square them: they always end up non-negative (also coincidentally why the square root of a negative number is not a real number). So we can define the length of the vector to be the square root of the sum of the squares of the vector's deltas.

If you imagine a segment to be a vector, then you can compute its length in exactly the same way. Length doesn't depend upon the position of the segment. That's why it works to think of the segment as a vector in this case.

OMG Do I Have To Know This Stuff?!?

If you already know about all the kinds of numbers, then you can skip this section. However, just bear in mind that I had to know about all these things before I could develop Painter! And now it's your turn! Waahahahahaa!

There are various kinds of numbers that it is useful to know. The integers are the whole numbers, zero, and their negatives. On a computer, there may be a smallest integer and a largest integer. That is what we like to call an implementation detail in the business. If you need more accuracy, you might want to use a real number. Real numbers can represent the integers, and all the numbers in between as well, like 9.57212947621.... On computers, these are represented by things called floats and doubles. These have various numbers of bits of accuracy.

When you divide one integer by another integer, you get a rational number (but please don't divide by zero!). There is really quite a spectrum of numbers that can be represented by rational numbers, called a Markov spectrum (but I digress). On a computer, real numbers can't really represent all rational numbers with 100% accuracy. For instance, you can represent 123/128 exactly, but 1/3 is hopeless to represent accurately. This turns out to be true because computers use power-of-two (binary) representations, and 128 just happens to be two to the seventh power.

Some numbers can't be represented exactly as a rational number or by floats and doubles on the computer. One example of these is an algebraic number: a number that is the root of some polynomial with integer coefficients, like the square root of two. If a segment has its endpoints at points whose X and Y are integers, then the segment's length is an algebraic number.

Another example is a transcendental number. Such a number can't be represented as an algebraic number or a rational number. Well, pi and e, the base of natural logarithms, are two examples of transcendental numbers.

OK, computers really only approximate these, but it's good enough for government work.

Back to the Vector

A vector then has a length and also an angle. Mathematicians have for ages thought of angles as being rooted in a vector that points east. This is the zero angle, and it corresponds with the X axis. Angles increase counter-clockwise, starting at zero and increasing until they become 360 degrees back at the X axis again. Although mathematicians actually think in radians. A radian is about 57.3 degrees. This means that 360 degrees is actually two pi radians.

Pi, by the way, is the magic ratio of the circumference of a circle to its diameter. It has a value of about 3.14159.... Yes, I memorized pi to 100 places and I used to recite it. Jeez, was I a geek!

But radians are a pure mathematical way of looking at things. Using radians instead of degrees saves you a multiply each time you do a trig function. Uh-oh. Trig functions!

Well, anyway, when you have a vector, and you divide its X and Y components by its length, you get a unit vector that points in the same direction. This unit vector consists of the cosine and the sine of the direction angle, by the way.

I remember when I was introduced to this fact. It was, to me, an "aha" moment. Now I understood why trigonometry was important! Actually, a few things fell into place that day in 1974. I ended up using it later on a test given to me by Joe Sukonick, a clever programmer at Calma Company. That bearded MIT graduate fellow ended up with a patent on the XOR for cursors in raster systems, by the way. But it was another guy at Calma, Tom Schaefer, that taught me some really useful things about analytic geometry. Without this information, it would have been seriously difficult to create Painter, or build the mosaic brush. Or really anything I do today.

What's Dot?

At Calma, segments definitely got connected end-to-end to create polygons. Calma built very good CAD (computer-aided design) systems for the very first VLSI (very large scale integration) components. In other words, microchips like the Motorola 68000 were designed on our systems. Yep, the original Macintosh's CPU.

I remember thinking about the notion of concave and convex and clockwise and counterclockwise. How could I determine these attributes for a polygon? It seemed like concavity was a local thing, and could be determined by looking at three consecutive points. But clockwise and counterclockwise were much more complicated, and were clearly a global thing. Or were they?

So there I was at the tender age of 19 at Calma, thinking abstractly about analytic geometry. It turns out I was smart enough and up to the challenge!

Tom Schaefer clicked his pen a few times and then drew a few figures on a piece of Calma stationery. Tom Schaefer was responsible for the all-angle fracturing software that enabled e-beam devices to render arbitrary geometries onto silicon, so I believed he could help me.

First there were three points, P1, P2, and P3. You could subtract the points' X's and Y's to make two vectors, V1 and V2.

But note that, the two vectors, if rooted at the same origin, created an angle between them, called theta. The angle is measured in counterclockwise degrees (or radians!).

That's when he introduced two operators, dot and codot. Dot is really the dot product and codot is sometimes called the scalar cross product. I found the operators' definition to be unusually simple and low-cost computationally. You just multiplied the X and Y components of the two vectors together in different ways. Wow!

Then he proceeded to show me that these operators could actually be used to compute the sine and the cosine of the angle theta. It was all beginning to come together. But I was a little hazy on my trig, so he made it absolutely clear to me. It's all about which side P2 is with respect to the line that passes through P0 and P1.

In fact, the sign of the codot could be used to determine this useful bit of information. And here's how to do just that.

OMG I thought this was incredibly clever. With this one operation, I could decide if a polygon is concave or convex, and even whether to not a polygon was clockwise or counterclockwise (as long is it's not self-intersecting).

But, of course, my brain was thinking several steps ahead.

It also occurred to me that, if V1 and V2 were unit vectors, that the dot and codot operators would simply produce the cosine and the sine of theta directly. In fact, I could see now that the rule about a vector's angle was simply a special case of this.

The dot product, it turned out, was useful in determining whether the two vectors were pointing in the same basic direction (if the dot is positive) or the opposite direction (if the dot is negative). And, by the way, if the dot product is zero, then the two vectors are at right angles to each other (perpendicular).

Area, Orientation, and Lobster Bisque

Polygons are a connected and closed chain of points in the plane. Between any two neighboring points is a segment. So, how do we compute the area of a polygon? Well, we make use of a clever technique called the trapezoidal rule. If a polygon is clockwise, then we just have to make trapezoids from each segment by dropping lines to the Y axis as we see in this diagram. Note that, on the bottom of the polygon, when the segments are going in the other direction, then the trapezoid areas become negative, because the X terms are going from right-to-left instead of from left-to-right as they are here. And that makes polygon area work by first computing the integral under the top of the polygon and subtracting the integral below the bottom of the polygon.

This has an interesting side effect. The clockwise polygons have a positive area and the counterclockwise polygons have a negative area.

So, really, to get the area, we have to take the absolute value of the computed area. And the sign is the orientation of the polygon. This turns out to be a very convenient way to compute polygon area! Once you see it, you will wonder how it can be so simple.

This turned out to be a question on Joe Sukonick's aptitude test at Calma. I took that test, and I got it right. But another guy, Bruce Holloway, got the job. Because, I was going to college at Caltech. The very next spring, when in Chemistry lab at Caltech, I got a call from Art Collmeyer. He saw the test and decided I might be interested in a summer job at Calma. It's good he called. I met Tom Hedges at Calma.

Oh, and by the way, the lobster bisque at Hula's Grille in Santa Cruz is excellent!

Knots

Knots are entanglement. They serve to bind, to secure, to tie. But the complex bonds that they represent are more than just bonds and complexity. There is actually a science to them.

Their overlapping, interweaving character is what makes them secure. Because of it, they don't fall apart. If you take one strand, you can't pull it away because it's entangled in the knot. This is one simple definition of a knot: no one strand can be removed without untying it.

In mathematics, a knot is a loop. The loop is officially embedded in three-dimensional space, but you can also embed it in the plane, if you consider, in addition, the crossing.

The overhand knot shown above is actually a trefoil knot with one cut. It is crucial to realize that any knot can be untied if the strand is cut.

In the real world, knots may be composed of more than one loop as well. An instance of this is two loops interlocking. Or the small weave is another good example.

Knots are important to sailors because ropes tie all things on a ship. Sometimes, like in the figure eight bend knot which can connect two ends of rope, they are designed to be strong, and yet untied in an instance so the two ends of rope can be disconnected.

In mathematics, again, there is a notion of a prime knot. This is a knot consisting of a loop that is indecomposable into a simpler prime knot. Each prime knot is defined by the number and configuration of their crossings. Cut the loop once and you can untie it.

The trefoil knot is the only prime knot with three crossings. It is one of the prototypes for the Valknut (along with the Borromean rings), a knot from Norse mythology. In the mathematical world, it is the simplest prime knot.

A simple figure-eight may be twisted and turned into a simple loop, called the unknot.

If you cut it at any place, you end up with the standard overhand knot, which is a knot in the middle of a single strand, used to thicken a strand so it might stay in place, for instance. This is called a stopper knot. A better stopper knot is the figure eight knot. Over, under, around, and through.

Some knots are really just intertwining of multiple strands. But these are not prime knots. A typical example of this is the simple 3-braid. This consists of three strands that are interwoven.

Pippi Longstocking (Pippi Långstrump in Sweden) probably braids her red pigtails this way. As did the Viking women more than a thousand years ago on Gotland.

Given three fibers, pretty much everybody knows how to make a braid. But really a braid can be made out of any number of fibers. In fact, the copper wire shielding on coaxial cable is braided in a pattern that wraps around in a circle, so it represents a higher-order of braid with a cylindrical connectivity. This kind of braid is less embeddable in the plane than, say, the 3-braid shown here.

In some ways, braids are a degenerate form of a weaving. But knots aren't really.

Knots are interesting to tie from rope. They have several uses. For instance, you can make a loop at the end of a rope for securing the rope to an object. This is a common knot, the slip knot. It has the distinction for being less secure than other knots made for the same purpose. For instance, the noose (shown) is a more secure loop end.

This is because, when you make a slip knot, it is important to take care that the part that slips is not the loose end. Otherwise it will slip right out. As you can see here, you make the connected end the part that slips and when you pull on it, it will become tighter.

To a point. And then the loose end will eventually pull through. Which is why a real noose additionally secures the loose end in some way. Using a figure eight knot as a stopper knot on the loose end is a good way to make sure it won't slip through eventually.

This is a very simple utilitarian knot.

But if you really need a good stopper knot at the end of a rope, try the double overhand knot. This knot is a bit larger than the overhand knot, more secure than the figure eight knot, and it's also probably easier to untie when you need to.

The double overhand knot is like an overhand knot, but you pass the loose end through one more time than usual. Once you have made the knot, then pull it tight and it makes a tight ball at the end of your rope that is very secure. It looks like the knot shown here. It makes one of the best stopper knots. When you don't want a rope to pull through a hole, you use this one.

It's secure enough to use when climbing, for instance.

If you want to learn how to tie proper knots, you can use the animated knot site, or their animated knot how-to apps.

Cryptography?

Anyway, knots are fun, and they have a mathematical basis that is even useful for cryptography. Imagine a digital signature scheme using a braid group, for instance. You can come up with standard notations for the prime knots also. More complex knots can be found to be decomposed into connected sums of prime knots. Unfortunately this is hard, like factoring numbers. And this is another reason why knot theory is sometimes used for cryptography.

Knots form groups and groups can be the source of endless interest.

Knot theory has often been identified by physicists as a basis for the process of quantum entanglement and other natural processes that occur at the subatomic level.

It seems that there is more to knots than meets the eye!

Patterns, Part 2

Back in 1993, I tested a special capability that, unfortunately, has since disappeared. It allowed you to devise patterns that used a set of basis tiles, so that each tile could be chosen from this basis set. I call these tiling grammars.

At the right is an example of such a pattern. When I write pattern, I mean a non-repeating arrangement of items taken from a small set.

In this case, you can easily see how a space-filling curve can be generated from a small set. But what isn't really obvious is that this image is made by randomly placing square images into a grid.

Each grid element can have one of two images in it. With this image, I have taken care to create an image that (almost) doesn't have any obvious loops in it.

Well, OK, it does have one, in the lower left corner. But it doesn't have any circles in it. That, it turns out would be legal in this particular pattern grammar. Loops (and loops within loops within loops) would also be legal.

Here is the basis set for this particular image. It consists of two tiles as you can see. In each square, one tile connects the middle of the top edge with the middle of the right edge and also connects the middle of the left edge with the middle of the bottom edge. The other tile is either a mirror-symmetry of the first, or it is rotated 90 degrees from the first, whichever you like.

But wait, there are more options along these lines. For instance, I can create two more tiles that connect vertically and horizontally. In one tile, the horizontal crossing takes precedence, and in the other, the vertical crossing takes precedence. Now what would happen if we randomly expressed a tile from this basis?

Well, we can easily generate this test as well. Here, to the left, we see that suddenly, this image is starting to look like a subway map.

This grammar can generate interweavings of any kind. Weavings are made of warp (vertical threads) and weft (horizontal threads). Since one element is warp-over and another element is weft-over, we can represent all possible interweavings.

But what makes this interesting is that the threads can also turn.

You can represent knots as well, of course, since we include pass-under and pass-over elements.

Suddenly, this pattern has taken on more dimensions than before. Just 4 elements and so much richness of representation!

I thought on this, and realized that I could also include ends: threads that do not cross the tile, but rather end. I increased the basis by 4 more tiles. This time, the four diagonal sad-faces were added.

It is not obvious to me what this grammar will generate. But I think it's going to be interesting nonetheless! This seems to leading to noodles and other patterns made of threads that have ends. What will it look like?

Here is an example output randomly from this grammar. The most interesting part is that the complexity has definitely increased. Notice that the threads seem to look like bacteria in a culture mold. But regular, of course.

One obvious thing is that dots have appeared. And letters, like lower-case f and t.

You can identify each thread by itself, and where it goes.

And yes, a sad face has appeared in upper right.

After making this, it occurred to me that it would be possible to add 3 more elements to the basis. A tile containing 4 ends, and horizontal and vertical crossings with ends on the other sides of the tile.

Here is the new basis set, with the three new tiles added.

Perhaps the new elements look like the division symbol. But with the interconnections, this will likely be obscured by the neighboring elements, hiding it.

One thing we can say just by looking at the basis set: there might be more dots than in the last generated example. And more vertical and horizontal lines, particularly those which have no other line crossing them. So this will undoubtedly lead to more open space in some areas.

Here is the result of generating a random placement using this new basis set.

The result is using fewer and fewer curves. There are twice as many free-floating dots as in the last one.

One thing to remember is that each previous level is really just a subset of this next level.

Perhaps even more interesting than ends is the possibility of branching. We can assume that there are no curves and try to construct a maze grammar.

This would not have crossings, per se, rather it would be more square, with cross, the four t's, horizontal and vertical paths, with ends as well, but not really circular or curved. It occurs to me to try this case.

Here is the new basis, that operates only horizontally and vertically, and contains branching. I don't think it could generate a maze, though. On the average, it will probably generate circuits (closed loops).

This grammar is very foursquare. I have rounded off the edges to make it a little more presentable.

Here is the result of generating a random placement from this basis set.

It is a very busy pattern with very few dots. It does tend to be a little maze-like, and the pieces in it are heavily connected.

The tiling grammars I have presented here are reminiscent of Wang tilings.

Perhaps they are even closer to Thue-Morse tilings.

All of these are related to the work I did back in 1993, when the image hose was just invented and I realized that it might bear on this class of tiling grammars.

Prime Numbers

When you need to keep a secret, it's all in the numbers. The prime numbers.

Number theory is the basis of many cryptosystems these days. The famous RSA public-key cryptosystem is based on computing a number that is the product of two large primes. And because that number is hard to factor, your secret is safe.

When I was a kid, I became interested in numbers. It started when I read The Lore of Large Numbers, by Phillip J. Davis, first published in 1961. There was also Mathematical Recreations and Essays, by H. S. M. Coxeter and W. W. Rouse Ball. This led to unusual things like memorizing pi to 50 places, so I could recite it at any time. And I am sure I impressed my parents to death by reciting it. I can still hear the cadence of the digits in my head. Pretty soon I became interested in computation.

I often used to ride my bike to the San Jose State Math Library to pore through its stacks of math periodicals. I was especially interested in the Journal of the Mathematics of Computation (known as J. Math. Comp. in the biz). You can access the back issues of this journal online.

Yeah, to say that I was a nerd might have been understating the issue! But my obsession led to an interest in computation and, in particular, such things as prime numbers, factoring, and continued fractions.

Also, remember that this obsession happened in the late 1960s, before I even touched my first computer.

Prime Numbers

You can think of prime numbers as the basis set for all integers greater than 1 because every such integer can be formed by the product of primes. Kids first get exposure to prime numbers in the fourth grade (or earlier) when they learn to reduce fractions.

You probably know that the prime number sequence starts with 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...

The prime number sequence thins out as you get to larger and larger numbers. This is obvious because with larger numbers, there are more and more factors that can possibly divide a number. The prime number theorem states that, as x gets larger, the number of primes less than x generally approaches x/ln(x). Note that ln(x) is the logarithm base e (2.71828...).

In any case, there are a lot of primes. There are, for example, 50,847,534 primes less than a billion. You can easily prove that there are an infinite number of them.

Meeting a Number Theorist

In the summer of 1972, I was in a program at UC Berkeley for promising high-school-age mathematicians, sponsored by the NSF and chaired by Professor Frantisek Wolf. Having studiously read J. Math. Comp. for years, one of my idols was Derrick H. Lehmer, one of the world's foremost number theorists. Professor Lehmer was at Berkeley at the time. One day Paul Gootherts and I worked up our courage and went up the his office in Evans Hall and introduced ourselves to him.

Imagine my surprise when I found that he and his wife Emma were packing up his office! He was retiring that very week. So I struck up a conversation with him. It seems that we were both looking at continued fractions and their use in producing approximations to square roots using irreducible rational numbers. His interest was in factoring theory. Apparently constructing the continued fraction for the square root of a number was useful in producing factors near to the square root of a number, which was in turn useful in a certain primality testing method he was researching.

I accompanied him to the computer lab in the basement of Evans Hall and watched as he loaded a huge deck of card into an IBM card duplicating machine. When it failed and destroyed some of his cards, he exclaimed, "oh, lord! it's eaten my cards!". Of course, no one was more passionate about the use of computers in mathematics than Lehmer.

His wife Emma was apparently from Russia. I noticed that she had dozens of Russian volumes on the shelves in their joint office. I also spoke with her because I had read her paper on repunit primes. Repunits are decimal numbers consisting only of a long chain of 1's. An obvious factor of 10^n - 1.

They were surprised to say the least to find a 16-year-old kid with such an interest in number theory.

My friend Paul Gootherts had implemented a multi-precise arithmetic package in Fortran that we had run many huge calculations on, using a reasonably-fast Control Data Corporation computer that he had timeshare access to. So there was plenty to show and talk about. We had brought our books of calculations. I think we had calculated the cube roots of the first fifty primes to a thousand places each.

Prime Quads

When, for a given integer n, four numbers of the form 30n+11, 30n+13, 30n+17, and 30n+19 are all prime, they are collectively called a prime quadruplet. This is a very dense arrangement of prime numbers. Some ready examples are (11, 13, 17, 19), (101, 103, 107, 109), and (191, 193, 197, 199). I took a particular interest in this arrangement after looking at D. H. Lehmer's table of primes under 100,000. With my number-obsessed vision, they practically jumped out at me. Hell, they still do.

When I went to Caltech, I spoke with resident number theorist Marshall Hall about writing a program to find prime quads, which I did. It took advantage of the fact that the center number 30n+15 was a single number that you could subject to a barrage of tests. Divide it by a prime and compute its remainder. That remainder cannot be one of four values, otherwise one of the four numbers in the quad will be composite. It was an exceptionally fast method of determine whether a prime quadruplet seems interesting enough to try to factor all four numbers.

Because of my interest, Hall introduced me to the Markov Spectrum.

Factoring and Primality Testing

The dumbest way of factoring a number is simply to divide it by all the prime numbers less than or equal to its square root. But there is an easy way to speed it up: divide the number by another number that is the product of n primes. Then the remainder, which you design to be significantly smaller than the original number, may be divided by each of the n primes in turn, looking for a zero remainder. This process makes the search about n times faster. This is because the remainder is much smaller and thus the divisions into the remainder will take less work. You can organize this into a binary tree to speed it up even further.

These days, a number field sieve may be used to factor unusually large numbers. But, I suppose that you can choose a thousand-digit number and it simply cannot be factored on any known hardware.

In order for this technique to be useful, it is not enough that factoring is hard, but determining primality must be easy also. And it does appear to be easier than factoring, and these advances have occurred in the last ten years. In 2002, Agarwal, Kayal, and Saxena (AKS for short) found a polynomial-time primality test. It has since been improved by Bernstein and Lenstra. Unfortunately, even an improved AKS algorithm still takes about a year to determine primality of a 100-digit number.

But practically, a randomized algorithm such as the Rabin-Miller method for compositeness testing is, on the average, much faster. The Jacobi Sums algorithm is very practical, having been used to determine primality of exceptionally large numbers (up to 3395 digits). The Elliptic Curve Primality Proving (ECPP) algorithm has been used on a 15071-digit number, with a running time of 5.1 GHz-years. Of course, it can be distributed to multiple processors to speed it up. On ECPP, a 100-digit number takes about 2 seconds to prove primality on the average. Much faster than one year! The Rabin-Miller algorithm is feasible on numbers with a million digits, but remember that it can only produce a certificate of compositeness. But it is fast: a 300-digit number takes about 23 GHz-seconds to certify compositeness.

So, people have been combining the approaches, by doing a fast compositeness test in parallel with a primality test. In this way, the running time of primality testing (with an early-out for a composite number) is minimized.

Siri

Ever use Siri on an iPhone 4S? I have, and I find her tremendously useful!

Female Assistant?

Even if she wasn't connected to a bunch of knowledge bases, the value of having Siri recognize what you say and turning it into text is simply immeasurable.

And why do I ascribe her a gender? Because her voice is a very polite female on my iPhone. She is my personal assistant when I don't have the time to type into the tiny iPhone keyboard. When I need to take notes, I can use my earbuds with a built-in mike. (Note: for the British, Siri is a man, baby. You see, in the UK and France, Siri is male, while in America, Australia and Germany, Siri is female.)

So Much Easier

How do I use Siri? My main use for Siri happens when texting or typing in a note or an email. There is a little microphone icon in the keyboard. Just tap that icon and suddenly you can speak into it and it converts what you say into inserted text. So Siri takes excellent dictation, and you don't have to wait all afternoon to get it transcribed.

This helps when texting. Now, you should never text while driving, but if you are in the car at a stop light and your time is limited, Siri can help. When composing a long email, I have used Siri to get most of it in. Even when she can't convert all the text, it saves 99% of the time of typing. Bad words in the text? Select the words, hit the mike icon, and say it again.

Helpful Tasks #1: Just Waking Up

I recently had my Oregon Scientific timepiece fail in an annoying way. It is usually utterly dependable, since it syncs to the atomic clock transmitted by WWV Fort Collins Colorado and because it automatically updates to the Daylight Savings Time. I have been using this for setting an alarm for years and years and I would wake up to it. But the other day I accidentally knocked it to the floor and somehow the alarm time got reset to 12:00 AM. And that's not a good time for the alarm to go off! And let me say that the interface for setting an alarm on that thing is opaque to me. I tried everything, seriously. Groan.

As it happens, I charge my iPhone next to my bed, so I just started using Siri to set an alarm. "Set an alarm for seven AM" works just fine. Problem solved! But I will have to change the alarm sound to something other than that blaring klaxon!

You see, the iPhone syncs to network time (which also comes from the same source) and it also has the logic for updating itself automatically to Daylight Savings Time working perfectly. Apple's wonderful UI expertise to the rescue!

Helpful Tasks #2: Factoring Numbers?

For the second task, you are going to laugh. I am a closet mathematician, a number theorist. When I drive to work in Cupertino, I take Summit Road where the addresses are all 5 digits and to my right as I drive are the odd numbers. I doubt any of you share this hobby: factoring 5-digit numbers in my head. I just can't let one of those numbers go by without wondering what its factors are.

For me it just passes the time. And it keeps my brain working on interesting things while doing the boring driving. One 5-digit number sometimes takes a couple of minutes to factor. Others take longer. Sometime I will do a blog post on how I do this in my head, which will bore you to tears, I'm sure, but you don't have to be a genius to factor 5-digit numbers in your head the way I do.

Usually, when the traffic stops in Los Gatos, I check my answer by using Siri. I ask her "What are the factors of twenty three thousand four hundred ninety one?" and I get the answer. This is because Siri is connected to, amongst other databases, the Wolfram Alpha knowledge engine.

The reason I used the example 23,491 was because I actually factored it wrong in my head: I wasn't looking for the prime number 13 to divide it twice. But now my built-in algorithm works a little differently. Ahem.

How Does That Work?

The science and art of voice recognition has been steadily advancing over the years. The main hold-up to productizing the technology has been processing speech with no gaps between the words. Or is it the computational linguistics? Or detecting accents?

To combat all these complex variables, Siri apparently has a focused task. In plain language, she knows what you might be asking her for. There is another thing that matters: a phone has a close-up microphone and already has software and hardware designed to single out your voice and make it clearer. This is a huge benefit, and makes the task of speech-to-text much easier.

Another thing Siri has that makes interaction easier is name assignment: equivalencing. I can simply say "Tom Zimmer is my oldest brother" and now I can say things like "call my oldest brother" or "send my oldest brother a text". And it works! But don't expect her to be able to call your dead uncle.

And if you replace the user's name in the contacts list with a rude phrase, then some can be offended. So let's not do that!

Put an Accent On the E

I would be very interested to hear how Siri is performing in the non-English versions it supports: German and French. How does it respond to a Bavarian accent, for instance?

I know in English, accents can be troublesome. I also know that there is a British, an Australian, as well as an American version, so there is some allowance for accents. But Irish accents -- how do they perform? Not so good, so far.

However, I have seen a video where a fellow with a northern Indian accent uses Siri and it works just fine. It only stumbles when he tries to use an Indian word. But it got all the city names (and correctly understood that when he said Bombay that he really meant Mumbai).

If Siri doesn't understand your accent, you can type in questions to Siri using this technique. Just say a word, then click the word before Siri has a chance to answer. Voila! Text box and keyboard.

And what is my accent? Well, I live in California. So my accent is Californian. You see, I'm clever enough to not to claim that I have no accent. There are plenty of American accents. Perhaps some southerners have issues with Siri as well. How about Texans? I would love to know!

Helpful Tasks #3: Texting

Communication is important. In the car, wearing a Bluetooth headset is useful. And, so far, the cops won't pull you over for doing it, unlike when you use those highly noticeable white earbuds. But mind how you look. When you get a text, you can press and hold the headset button to get to Siri and ask her to read you the text message. Then you can text back in a similar manner.

This might not be as easy on a motorcycle. There is the road noise. And of course if you are using a helmet (I hope so!) then it's hard to hit that button on the headset. Are there solutions for this? Of course! Just use a Bluetooth helmet headset. With the mike and the earbud inside the helmet, the noise problems are managed better.

But, when I was just sitting in my car at lunch time, I have had chat conversations using Siri and they went spectacularly well.

When I first used an iPhone, I felt like I was holding the future in my hand. Each new iPhone gives me that feeling again, with GPS, retina displays and Siri: it's really more of the future brought to you first by Apple!

And check out that iPhone 4S camera too!