Wednesday, December 23, 2020

On the superpermutations of the family of multisets [1, 1, n]

Inspection of the preliminary results for this family which we discovered last time reveals that some of the minimal-length superpermutations of the multisets [1, 1, 2] and [1, 1, 5] are palindromic.

Conveniently, a brute-force search of the space of possible palindromic superpermutations is considerably faster than a brute-force search of the entire superpermutation space. This is because it is only necessary to find a string which contains half of the full set of permutations (eliminating mirrored pairs of permutations), which can then be mirrored to produce to the second half of a palindromic superpermutation. This requires checking (n/2)! orders in which to combine 2^(n/2) possible subsets of the full set of n permutations, but since the exponential function grows much slower than the factorial function, this turns out to be a net win.

It turns out that all members of this family have palindromic optimal superpermutations of a common form (some have multiple palindromic superpermutations). For n=1 through 9, the relevant results are as follows:

(Note that these examples have all undergone rewriting to ensure that digits have their initial appearances in increasing order, and the palindromic suffix is marked out with brackets.)

[1,1,1]: 12312[1321]
[1,1,2]: 112311213[12113211]
[1,1,3]: 11123111213112[1131211132111]
[1,1,4]: 11112311112131112113[1121113121111321111]
[1,1,5]: 111112311111213111121131112[11131121111312111113211111]
[1,1,6]: 11111123111111213111112113111121113[1112111131121111131211111132111111]
[1,1,7]: 11111112311111112131111112113111112111311112[1111311121111131121111113121111111321111111]
[1,1,8]: 111111112311111111213111111121131111112111311111211113[11112111113111211111131121111111312111111113211111111]
[1,1,9]: 11111111123111111111213111111112113111111121113111111211113111112[1111131111211111131112111111131121111111131211111111132111111111]

Each of these starts with n ones, followed by repetitions of the following pattern:

'2' '1'{0} '3' '1'{n-0} '2' '1'{1} '3' '1'{n-1} '2' '1'{2} '3' '1'{n-2}...

I.e., alternating '2's followed by x '1's, and '3's followed by n-x '1's, with x increasing by one in each chunk of symbols, up to n-1 chunks of ones.

This leads to a straightforward O(n^2) algorithm (because the final length is of order n^2, so it takes at least that much time to output the entire string) for generating minimal superpermutations of any multiset in the family [1, 1, n], with O(1) complexity for generating each subsequent symbol incrementally, with the lengths tightly following the previously determined lower bound for this family:

k = 2n + (n+1)(n+2) + 1

Tuesday, December 22, 2020

An initial exploration of superpermutations of multisets

 A superpermutation of a set is a sequence of n distinct symbols which contains all n! permutations of those n symbols as substrings. A trivial superpermutation just lists all possible permutations one after another, for a total length of n*n!. However, considerably smaller superpermutations can be achieved by overlapping permutations with common prefixes and suffixes.

Without loss of generality, we can label all of the elements of a finite set with integers, and work exclusively with sets of consecutive integers. Each set, and its corresponding set of superpermutations, can then be parameterized with a single number--its size, or cardinality.

The unique superpermutation of the set of size 1 is "1".

The superpermutations of the set of size 2 are "121" and "212" (which are equivalent up to relabelling).

And minimal-length superpermutations are known for sets of up to size 5.

But what if, instead of working with proper sets, in which each symbol must occur exactly once, we decided to look at permutations of multisets instead?

Multisets allow each element to occur any number of times, known as the multiplicity of the element. The (equivalence classes of) multisets are no longer characterized by a single number; instead, we can talk about the support cardinality (the number of different kinds of elements it has), the multiplicities of each of those elements, and the multiset cardinality, which is the sum of the multiplicities. All of that information can be encoded as an ordered list of multiplicities (which, for the sake of consistency and without loss of generality, we can assert must be non-decreasing). Thus, the multiset { 1, 1, 1 } can be represented by the list [3], and the multiset { 1, 2, 2 } can be represented by the list [1, 2].

This provides several different dimensions along which to extend the size of a multiset, with different implications for their effect on the superpermutation.

Multisets with all multiplicities equal to 1 are equivalent to sets of the same cardinality, and have the same superpermutations. Due to the repeated elements, however, multisets with multiplicities greater than one have fewer distinct permutations than sets of the same cardinality, and thus have shorter minimal superpermutations. In the trivial case of multisets with support cardinality 1, they have a single permutation (a list of their single element repeated as many times as its multiplicity), which is also the unique superpermutation--just like sets of cardinality 1.

Things get more interesting for multisets of the form [1, n], with support cardinality 2. These have minimal superpermutations of the form 2{n}12{n}--i.e., the second element repeated as many times as its multiplicity on either side of the first element. E.g., 

super([1, 1]) = 212, equivalent to the superpermutation of the set of cardinality 22
super([1, 2]) = 22122
super([1, 3]) = 2221222


Each individual permutation consists of inserting the first symbol somewhere in the list of repetitions of the second symbol, and can be obtained by sliding a window of length n+1 across the superpermutation, and the lengths of these superpermutations are trivial characterized by the formula L([1, n]) = 2n + 1.

If we move on to multisets of support cardinality 3, however, things suddenly get considerably more complicated. Adding only a single additional element with multiplicity 1 increases the number of permutations by a factor of n+1 (going from 3 for n=2 to 12=3(n+1) for n=3), as the additional element can be placed in every position in each of the previous permutations. Through exhaustive search, the minimal unique (i.e., with mirrored pairs and pairs which can be turned into each other via relabelling) superpermutations of [1, 1, 2] are


with a length of 17.

A conservative lower bound on the possible lengths of minimal superpermutations can be acquired by observing that the number of permutations achievable by sliding a window along the superpermutation must equal or exceed the number of distinct permutations of the multiset. The number of windows of length n over a string of length k, where n<=k, is simply k - n + 1. The permutations of a multiset S are given by the formula C(S)!/P(m! | m in M(S)) where C is the cardinality function, P is the product operator, and M is the multiplicity function; in other words, it is the factorial of the cardinality of S divided the product of the factorials of each of the multiplicities of S. Thus,

k >= C(S) + C(S)!/P(m! | m in M(S)) - 1

For the [1, n] multisets, this formula gives lower-bound lengths of 3, 5, and 7, respectively--so it is in fact a tight bound. For the multiset [1, 1, 2], however, this gives lower bound length of 4 + 4!/(1!*1!*2!) - 1 = 4 + 24/2 - 1 = 4 + 12 - 1 = 15--while the actual minimal length, discovered by exhaustive search, was 17. And in fact, it is easy to see that each of the superpermutations have 2 length-4 substrings which are not permutations of the multiset, accounting for the extra length. This is unsurprising, since it is already well known that this is not a tight lower bound for superpermutations of sets, and multisets are a strict superset of sets.

There are a few ways in which we could try to extend this result--increase the value of n again, to create a parameterized family of [1, 1, n] multisets; extend the number of singleton elements, to create a parameterized family of [1{n}, 2] multisets, with increasing support cardinality; or pivoting entirely to see what happens with [n, n] multisets, with support cardinality 2 and multiset cardinality 2n.

It turns out that increasing the number of unique elements increases the number of permutations much faster than increasing the multiplicity of an individual element. Trying to brute force [1, 1, 1, 2] (with 60 permutations) just causes my software to run out of memory and fall over and die. That could probably be fixed, but it makes it much easier to go in different directions for now.

The Family [1, 1, n]

Doing a complete brute-force search of the superpermutation space for n > 2 takes a very long time; however, some superpermutations closely approaching the lower bound can be found relatively quickly.

The multiset [1 1, 3] has a lower bound superpermutation length of 24. It appears to have optimal superpermutations of length 27 -- 3 more than the lower bound. An example is 332313323313233312333213332.

The multiset [1, 1, 4] has a lower bound superpermutation length of 35. It appears to have optimal superpermutations of length 39 -- 4 more than the lower bound. An example is 323331323333123333213333231333233133233.

The multiset [1, 1, 5] has a lower bound superpermutation length of 48. It appears to have optimal superpermutations of length 53 -- 5 more than the lower bound. An example is 33233313323333132333331233333213333323133332331333233.

Recalling that [1, 1, 2] had a minimal superpermutation length of 17 -- two more than its theoretical lower bound -- then assuming that this empirical pattern holds, this family appears to have optimal superpermutation lengths given by k = C(S) + C(S)!/P(m! | m in M(S)) + n - 1, which can be simplified to

k = 2n + (n+1)(n+2) + 1

The Family [n, n]

The multiset [2,2] has a total of 6 permutations, and a lower bound superpermutation length of 9. Its single unique superpermutation is


which has a single length-4 substring which is not a permutation of the multiset, and a total length of 10.

As with the [1, 1, n] family, doing a complete brute-force search for n>2 takes a very long time, but we can find probable solutions fairly quickly.

The multiset [3, 3] has a lower bound superpermutation length of 25, and an apparent optimal superpermutation of length 29. An example is 12221112221211221212122112122.

The multiset [4, 4] has a lower bound superpermutation length of 77, and an apparent optimal superpermutation length of 117. And example is 222121112222111122221121222111212221121212211122122111222121121221211221212112221122112211211222121212122112122211211.

The multiset [5, 5] causes my search process to run out of memory and fall over. :(

The multiset [1, 1], equivalent to the set { 1, 2 } has a minimum bound of 3, and an actual minimal superpermutation length of 3.

The differences from the minimum bound formula are 0, 1, 4, and 20 for n = 1, 2, 3, and 4 respectively.

Unfortunately, there is a large number of matches for the sequence 0, 1, 4, 20... in The Online Encyclopedia of Integer Sequences... and none for 3, 10, 29, 117. So, without a more principled method construction for these superpermutations, I am unfortunately at a loss to properly characterize them.

Friday, December 4, 2020

Why the Braid Group of Order 4 is the Best Braid Group

 See also: A New Kind of Algebra

Consider the braid group of order 1. It has a single element, the identity element "1", representing section of a single strand. If you stick them together... well, 1*1 = 1, and one untwisted strand stuck onto another untwisted strand just gets you... an untwisted strand. Completely trivial and uninteresting.

Consider the braid group of order 2. It has two generators (basic members which cannot be created by combining other members, but which can combine to create the rest) in addition to the identity element: a twist, and an untwist. This is already an infinite group, because you can make an unlimited number of new unreducible things just by adding more twists! But, it's still a pretty uninteresting one. The only elements are just powers of a single generator--because any sequence that contains both a twist and an untwist simplifies to one that doesn't.

Consider the braid group of order 3. It has four generators, because you can put twists between either of the two pairs of adjacent strands. And finally, you get some non-trivial structure, because twists on different sets of strands don't cancel each other out!

But now, consider the braid group of order 4. It has six generators, and commutative relations! Now you can actually get some interesting algebra going on. And if you continue on to the braid group of order 5? Nothing new. After 4, you just get more things that commute with each other. No truly new structure ever appears again.

Furthermore, if we select elements of B4 with specific interesting properties, we get an interesting number...

Suppose we take a subset of B4 such that all elements obey the rules of Celtic knotwork: i.e., any given strand must alternate between over-crosses and under-crosses; no single strand can cross over another or under another twice in a row. All six generators follow this rule trivially, because they are all single crossings. However, we can characterize the remaining members of this set rather simply: they are all of the braids which contain only sequences of the following pairs of generators:

  1. aa
  2. bb
  3. cc
  4. /a/a
  5. /b/b
  6. /c/c/
  7. a/b
  8. b/a
  9. /ab
  10. /ba
  11. b/c
  12. c/b
  13. /bc
  14. /cb
  15. ac (=ca)
  16. a/c (=/ca)
  17. c/a (=/ac)
  18. /a/c (=/c/a)
So, the entire set can be reduced down to 24 basic elements.

Now, imagine that we print the graphical representations of these elements out of cards, which we can physically manipulate. In addition to lining them up to concatenate them (equivalent to group multiplication), physical cards permit a new operation which is not part of the normal braid algebra: 180-degree rotation. Rotation has the following effect on each of the basic elements:
  • r(a)    = c     r(c)    = a
  • r(/a)   = /c    r(/c)   = /a
  • r(b)    = b
  • r(/b)   = /b
  • r(aa)   = cc    r(cc)   = aa
  • r(/a/a) = /c/c  r(/c/c) = /a/a
  • r(bb)   = bb
  • r(/b/b) = /b/b
  • r(a/b)  = /bc   r(/bc)  = a/b
  • r(b/a)  = /cb   r(/cb)  = b/a
  • r(/ab)  = b/c   r(b/c)  = /ab
  • r(/ba)  = c/b   r(c/b)  = /ba
  • r(ac)   = ac
  • r(a/c)  = c/a   r(c/a)  = a/c
  • r(/a/c) = /a/c

So, suppose that we wanted to build a deck which could provide any of these 24 elements with the minimum number of cards. For any rotational pair, we only need to print a single card, since we can get either member of the pair depending on which way we lay it down. That eliminates 9 elements, getting us down to 15. (It's on odd number because one pair of inverses rotate into each other: a/c ~ c/a.)

If you remove double twists, because they just aren't as cool, that gets you 11 basic cards--which is few enough to fit into the space of a 13-card suit in a regular deck! Thus, you can do Celtic braid algebra on 4 strands by assigning a simple braid value to each of a set of regular playing cards, with two left over--and you get four copies per deck, so you can actually do interesting things!

Go up to order 5, and the number of basic Celtic sequences is considerably larger, so even by throwing out double-twists, you can't get it to fit into a normal card deck nearly as nicely.

Saturday, November 28, 2020

A New Kind of Algebra

Suppose we have two "things": a and b. We don't what they are, but we have labels for them. Like any other algebraic variables, we can multiply them by putting them next to each other: aa, ab, ba, or bb. Since we don't know what these things are, we can't assume that their multiplication is commutative; i.e., ab does not necessarily equal ba. So, aa, ab, ba, and bb are four new unknown-but-labelled "things" that are generated by multiplying our original things.

We can also define multiplicative inverses, /a and /b, so we can do division. I general, multiplicative inverses aren't guaranteed to exist, but in this case, we can just assert that they do. Thus,

a/a = /aa = b/b = /bb =1

So, we can now generate additional new things named a/b, /ba, b/a, /ab, /a/a, and /b/b.

Additionally, since we have defined a thing times its inverse to equal 1, given a string of things like a/bba, we can simplify it to a1a = aa. Or, for something a little more complicated, we can simplify something like ba/bb/ab to aa1/ab = aa/ab = a1b = ab. Note, however, that because multiplication in general is not guaranteed to be commutative, we can't simplify a/bab or baa/b--the a's get in the way between the b and its inverse.

So, we can simplify things, but not very interesting things--we can only insert and remove sequences where items and their inverses are right next to each other. So let's add a third thing: c, and it's inverse /c. And, we'll assert some special properties of c:

ac = ca
a/c = /ca
c/a = /ac
/a/c = /c/a

In other words, c and its inverse multiply commutatively with a and its inverse. All other combinations are non-commutative.

Now, we can simplify things like a/bc/cba to a/b1ba = a1a = aa, as before; but we can also do things like baca/c/a/a. Note that nothing is adjacent to its inverse, but because of the commutativity rules, we can re-arrange things to put them next to their inverses: baca/c/a/a = baca/a/c/a = bcaa/a/a/c = bc/caa/a/a = ... = b.

Now, suppose we have two more complicated expressions that we want to multiply together; e.g., perhaps we want to square acb/a/c. By itself, it can't be simplified, because the b does not multiply commutatively, so it blocks re-arrangements of the a's and c's to allow cancellation. But when we square it, we get acb/a/cacb/a/c = acba/ac/cb/a/c = acbb/a/c.

Now, having introduced these unknown things and their algebraic properties... what's the point? Clearly, these things aren't regular numbers--do they correspond to anything familiar?


It turns out that a and b behave exactly like (and thus, mathematically are) the generators of the braid group of order 3. In other words, If you have three parallel pieces of string, a is the name we give to twisting the first and second strings in a particular direction; b is the name we give to twisting the second and third strings in the same direction; /a and /b are the names we give to twisting those same pairs of strings in the opposite direction; and any three-strand braid can be algebraically described by some sequence of a's, b's, and their inverses. 1--the multiplicative identity--represents a section of straight, untwisted string. a/a = 1 because twisting a pair of strings and then untwisting it results in... untwisted, straight string. Same with /aa, b/b, and /bb. A typical braided hair ponytail is just a sequence a/ba/b, repeated over and over... or b/ab/a, to get the chevrons pointed in the other direction. Multiplying a's and b's together is not commutative because a twist in the first and second strands shares a strand with a twist in the second and third strands, so you can't slide them past each other to change their order.

Adding c gives you the three generators of the braid group of order 4--that is, a way to describe braids with 4 strings. So, why does c commute with a? Because a twist in strings one and two doesn't share any strands with a twist in strings three and four! So, you can slide them back and forth along their respective pairs of strings to change their linear order.

Thursday, December 19, 2019

On Religious Sacrifice

This is the fourth in a series of posts derived from old Facebook notes. As it happens, this particular topic happens to be topical again! The original was posted on September 3, 2013.

A friend-of-a-friend post showed up in my Facebook newsfeed once that rather bothered me. Some guy I don't know posted a link to an article about the LDS-church-owned City Creek Mall, along with a bunch of (unexplicated) Bible verses on hypocrisy. This of course set off a rather extensive and heated discussion in the comments (which resulted in it showing up in my news feed when a friend commented).
The primary point of discussion was whether or not it was appropriate for the church to be involved in commercial ventures. As though capitalism and creating wealth are somehow inherently anti-spiritual? That it is possible to run a business and to be a good person at the same time, and, furthermore, to use the proceeds as an enabler of greater amounts of good in the world than could be accomplished if you were poor, is so incredibly obvious to me, and I find myself so utterly incapable of fathoming the minds of people who could think otherwise, that I really don't know how to argue this point. If you are not LDS, think what you will; if you are, chill out, dudes, and just trust that people in charge know what they're doing even if you don't get it yet.
Of course, with the recent news items about how the church has billions of dollars stashed away in reserve, the same kinds of issues are coming up all over again. Somehow, it's a shocking, outrageous thing for a church to actually >save money. Instead of, what, spending all of its assets on immediate distributions to the poor (something which the critics, of course, aren't actually doing themselves), and being left with nothing in reserve and no ability to continue to do further good?
Another common concern, however (and the source of the title of this note), seemed to be "was my tithing money used to pay for that!?" (Spoilers: At last in the case of City Creek Mall, no, it wasn't.) Followed up by agitated remarks about how "I expect my tithing to be used for..." whatever, building churches, helping the poor, etc. In short: If you are worried about what your tithing money is being used for, you are doing it wrong. Or any other donations, for that matter.
The Church should be accountable for how it uses its funds. And it is. That's why it has an auditing department. And it does in fact do a good job of being pretty transparent about the important, large-scale stuff--hence, I know that City Creek Mall was not built with tithing money. It's not completely transparent, 'cause it doesn't have to be, and mandating that would actually add to administrative overhead and lead to worse wastage of the sacred money that everybody is so worked up about. But we know what kinds of things tithing money is used for. We know what kinds of things fast offerings are used for. And we know what kinds of businesses the church owns. Nevertheless, the fact that you can go and look that stuff up is not for your benefit--it's for the Church's benefit, to ensure that the Church organization is kept in line. The emotional benefits to members of the general populace due to the fact that they must be allowed to know some of this stuff as a requirement for preventing mismanagement are purely ancillary. In other words, it's nice that you can find out a little bit about how tithing and other donations are and aren't spent, but you really shouldn't ever need to care. You shouldn't need to care anymore than you care about how your next-door neighbors manage their budget, because it's not your money.
This is because the whole point of paying tithing is to give it up. If you think along the lines of "I expect my tithing to be used to (x), not (y)", or even just "they better not be using my tithing for (z)" you have not actually given it up. Indeed, I would go so far as to say that you have not actually paid tithing at all, despite what the donation slip says--rather, you've granted the church some of your money with additional contractual stipulations known only to you in your head, and that's a very different thing. Members aren't commanded to pay tithing to finance the Church (although that's a wonderfully practical side-benefit, much like the emotional security of being able to look at financial reports)- members are commanded to pay tithing because members need to be taught to give things up to God. And the Church could accomplish that purpose regardless of where the money goes afterwards. It just doesn't matter. If 50% of the tithing budget were allocated to gold-plating all church-owned buildings and vehicles and the other half to powering the furnaces for Church office buildings by burning $100 bills (which will never happen, because see above about mismanagement, etc., but let's go with the hypothetical scenario), that should not change a single person's willingness to pay tithing or faith in the Church. If it would make a difference to you, clearly you need to keep paying tithing--you have not yet understood the meaning of sacrifice.
Furthermore, tithing is not a charitable donation. I mean, legally it is, because the church is, among other things, a charity-- but the commandment to tithe is not a commandment to give to charity. We have a whole separate thing for that--fast offerings. And giving to charity does not discharge one's responsibility to tithe. Tithing serves a completely different purpose--to teach you how to sacrifice, with a simple, concrete example. If we could all just figure that out, then maybe we'd be ready for the real deal-- the real law of sacrifice, and total consecration of all we have to the Lord.

Everybody is Smarter Than You Think

This is the third in a series of posts derived from old Facebook Notes. The original was posted on Nov. 7, 2010.

  1. I am imperfect at translating my thoughts into speech that can be unambiguously parsed by an arbitrary second discourse participant.
  2. Due to (1), I have frequently witnessed people respond to things I say in a manner that makes it obvious that they did not reconstruct the thought that I started with properly (i.e., they didn't understand what I was trying to say).
  3. This probably makes me seem less intelligent than I actually am, especially when the misunderstood versions of my thoughts are, in fact, wrong. Either factually wrong, or indicative of an immature point of view.
  4. I put a lot more thought into what I say in order to ensure accurate communication than most other people. (Although this is probably tempered by the fact that I am not neurologically typical, so I kinda have to.)
  5. Due to (4), most other people are probably at least as likely as I am to have the same experience with being misunderstood. The less intelligent they actually are, the more likely this is to be their own fault; the more intelligent they are, the more likely it is to be because the other discourse participants are simply incapable of formulating the correct thought (but, of course, high general intelligence does not imply high social intelligence, so it could still easily be your own fault, insofar as not knowing your audience is your own fault).
  6. Ergo, most people you talk to will seem, at least until you get to know them very, very well, much less intelligent than they actually are, because what you think is going on in their brains is a very degraded version of what they're actually thinking.

In short, language is a noisy, imperfect channel for thoughts. So give people the benefit of the doubt.

Tuesday, November 12, 2019

Asymmetric Cryptography For Those Who Only Know Arithmetic

This is the second in a series of posts adapted from old Facebook Notes. The original was published on February 8th, 2011.

Let's start with basic substitution cryptography, and take baby steps all the way to asymmetric public key cryptography.

The simplest sort of cipher that nearly everyone is probably familiar with are alphabetic rotation ciphers (like rot-13). The key is how many letters you're going to rotate by; i.e., for rot-13, you rotate by 13 letters, so to encrypt an 'a', you count 13 spaces along the alphabet from 'a' to get 'n', to encrypt a 'w' you count 2 spaces down to the end of the alphabet and then the remaining 11 spaces down from 'a' to get 'j', and so forth. Mathematically, this operation is known as "modular addition", or "clock addition" (because numbers wrap around like the hours on a clock face). Except in the special case of rot-13 using the 26-letter roman alphabet, where adding 13 twice gets you back to where you started, the decryption function is different from the encryption function--you use modular subtraction instead of addition, counting backwards instead of forwards to reverse the encryption.

Now, rotation ciphers are so simple that they're only really useful at all if your potential attackers don't know that you're using it, but for most ciphers of this general category you assume that the functions are well known and the basis for security is keeping the key secret. If anyone finds out your key, you're screwed. And keeping the key private is a big problem with this sort of encryption (which was pretty much the only kind of encryption around for most of history), because you have to share the key with the person you want to talk to, and the key has to be sent "in the clear" (because you haven't shared it yet, so you can't encrypt it).

Not the features of this kind of cryptography: the encryption and decryption procedures are public (everyone knows how to count letters in the alphabet), they are asymmetric (encryption involves adding, while decryption involves subtracting), and the key is private and symmetric (encryption and decryption use the same key).

Now, instead of keeping my key private, I could not worry about the key and just keep the decryption function private. In fact, I might just do away with a key entirely; an example of this is the use of invisible ink (although that's really a better example of steganography than encryption). The message can only be decrypted if you know the secret decryption function (chemical process) for the relevant type of ink. And if I'm content with one-way communication, I don't have to share the secret. I can make the key and the encryption function completely public, and just keep the really-hard-to-find decryption function to myself, and then anybody who wants to can send me a secure message that only I can decrypt. If I want to go two-way, then my partner will have to come up with his own set of public encryption and private decryption procedures. Using a rotation cipher isn't very practical here, because figuring out how to reverse modular addition with modular subtraction is really easy, so your secret function wouldn't stay secret for very long. You can imagine functions that are harder to figure out, but since finding new mathematical functions with the right properties is rather difficult, this system is not very practical. It does not make sense for everyone who wants to send private messages to have to do serious research in pure mathematics!

But what if we made the key asymmetric instead of (or in addition to) the encryption and decryption procedures? With a rotation cipher, one way to do that would be to say that if, e.g., my encryption key is 5, then my decryption key is 21, and we're always going to use modular addition, symmetrically, to encrypt and decrypt. You add 5 to each letter to get the ciphered text, and then you add 21 to each ciphered letter (completing a 26-space trip around the alphabet) to get back to where you started. Now, you can do one of two things:

  1. You can publish your encryption key, and keep the decryption key secret. That means other people can encrypt messages that only you can read.
  2. You can publish your decryption key, and the encryption key secret. That means you can write messages (digital signatures) that other people can prove came from you, because decrypting it with your published decryption key works, and no one else is capable of doing that kind of encryption.
Now, that eliminates the key sharing problem! You have to keep something secret, but it really can be secret--you never have to share your private key with anyone. But, by using your public key, your friend can write messages that only you can read, and by using your friend's public key, you can write messages that only they can read. And it's easy to come up with new keys--much easier than inventing whole new mathematical functions!

Of course, a system based on simple modular arithmetic still isn't all that secure, because finding an additive inverse is *really easy*; in normal arithmetic, you just stick a negative sign in front (i.e., the additive inverse of 5 is -5), and in modular arithmetic you just subtract from the size of the alphabet (so the inverse of 5 in an alphabetic rotation cipher is 26-5 = 21). As soon as you publish the fact that your decryption key is 21, anyone can do some simple subtraction and figure out that your private encryption key is 5, or vice-versa. But, there are lots of mathematical operators and functions which have the nice property that some numbers have inverses in relation to those operators--not just addition. For example, the inverse of 2 over multiplication is 1/2, etc. Now, finding multiplicative inverses isn't all that difficult either, but it's a little harder than just sticking a minus sign out front, so let's run through an example using multiplication as the encryption function:

Say my public key is 2. Multiplying letters doesn't make immediate sense like counting them does, so we need to convert our letters into numbers first; fortunately, computers already represent letters as numbers anyway. So, suppose you want to secretly send me the letter 'c', which we'll assign the number 3. So, you use the encryption function (*) and the key (2) to calculate the ciphertext (3*2=6), which you send to me.
My private key is the inverse of 2-- 1/2.
I get the ciphertext 6 from you, and use the encryption function (*) with my private key (1/2) to recover the plaintext (6*1/2 = 3), which I can then interpret as the letter 'c'. Ta da! We have just accomplished encrypted communication without ever sharing a secret key.

By now, the basic proof-of-concept, that there is a way to communicate privately without ever having to arrange to share a secret with someone ahead of time, should be clear--as long as all of your adversaries are toddlers who haven't learned arithmetic. The multiplication-based system is still easy to crack, because everybody learns how to do division and multiply fractions in elementary school. But what if we did modular multiplication? Say I want to encrypt the letter 'n', which is the 14th letter of the alphabet; multiplying by my encryption key gets us 28--but there is no 28th letter of the alphabet! Instead, we wrap around and get the (28-26)=2nd letter of the alphabet--so 'n' encrypts as 'b'. What's the inverse of that? In this case, it turns out to be 20: 20*2=40, 40-26=14, 14='n'. That was a little harder to figure out, so we're getting somewhere... but it wasn't *that* hard to figure out (if it were, we wouldn't be able to figure out our own decryption keys ourselves, which would be kind of useless!), and it turns out that you aren't actually guaranteed to be able to find an inverse all the time--it's only guaranteed to work if the length of your alphabet is a prime number (which 26 is not!), so you have to pick your keys carefully, which makes it easier for an attacker to just try all of the possibilities until they guess the right one.

Real cryptosystems, therefore, get a little more complicated in a few ways. For one thing, although not all encryption functions depend on the alphabet being a prime number, most do require it to be special in some way; additionally, we want keys to be big numbers, in a large range (not just 1 to 26), so that they are harder to guess. Thus, we use more complicated ways of turning strings of letters into numbers before doing arithmetic on them. And for another thing, we have to be fairly clever about finding special mathematical functions (more complicated than just modular multiplication) which have a special property that makes it easy to generate a pair of numbers that are inverses of each other, but really hard to figure out the inverse given just one number. These are called "trapdoor functions"--it's easy to open the trapdoor from one side, but really hard to climb back out from the other side! But if you can find such a function (like, say, modular exponentiation over a range defined by multiplying two large prime numbers), so that you can't figure out what my private key is despite having the function and the public key, and then bam, you've got RSA public-key encryption & digital signing! If you know the prime numbers used to generate an RSA key, finding the inverse is trivial, so we can make keypairs for ourselves easily--but inverting a key without knowing how it was made requires factoring a large number, which is much, much more difficult than just doing division or multiplying fractions! And that is what keeps your messages over the internet safe.

NOTE: In these toy examples, and in actual RSA, the private key is the inverse of the public key, and the public key is also the inverse of the private key. This makes them interchangeable, and let's you do signing & encryption at the same time (that's generally considered a bad idea, but it can be done). However, while this seems intuitive and natural, it is not necessarily the case. There do exist functions for which a=inverse(b) does not imply that b=inverse(a), in which case the keys are not interchangeable.

Also note that, if you can factor large numbers easily, RSA becomes really easy to crack, just like our toy examples using addition and multiplication (that's what all the fuss about quantum computers is about). But while RSA was the first public-key encryption system invented, it's far from the only one nowadays, and there are plenty of more complicated encryption systems that rely on functions not-quite-as-accessible to an audience who only know arithmetic in which finding the inverses of public keys is much, much harder still.