These days e-commerce depends on public key encryption; the most notable example of such a system is RSA (named after Rivest, Shamir, and Adleman). This type of cryptography depends on underlying computational problems for security, and the key to these methods is factoring of large integers.

The premise is that factoring a large, positive integer (with 150 digits, let us say) is difficult. A natural question is whether the problem is exponentially difficult (that is to say, does the problem require about e¹⁵⁰ calculations, or rather p(150) calculations for some polynomial p?). It is in fact known that factoring large integers is a problem of sub-exponential complexity: the factorization of an integer with n digits takes not more than (about) exp(n^1/3) steps. In plane language, it could take several months for a high-speed computer to factor a 150-digit number.

It is interesting to compare the following two problems:

Suppose that I give you two 75-digit primes. Calculating their product, to produce a composite number of 150 digits, is straightforward and only takes a few thousand calculations.

If instead I give you the 150-digit integer from the first problem, finding the prime factorization is very difficult, and may take about exp(n^1/3) calculations.

The first problem here is of polynomial complexity, while the second is in the famous NP class.

Problems that are known to be of exponential complexity are a bit hard to come by. The traveling salesman problem (of planning a salesman's routes to a set of cities) is not known to be exponentially complex. The integer-factoring problem is not known to be sub-exponentially complex. There are problems in Presberger arithmetic (an arithmetic that contains addition but not multiplication) that are known to be exponentially complex.

There are known upper bounds for the order of complexity of the factorization problem (and these are of sub-exponential size), but no known lower bounds. The usual computer science techniques do not apply to resolve this issue. In practice in cryptography we would like to know what happens "most of the time." This requires a new set of techniques.

Now let us return to cryptosystems. In fact if a cryptosystem can be cracked 20% of the time, then the system is in effect unusable. It is not effectively secure. So it useful to think about "worst case complexity," "average complexity," and "generic complexity." The focus of this workshop is on the last of these.

Generic complexity is measured by a standard device from number theory. Consider the set of of words in a 2-letter alphabet. Let S be a subset of these words. We can ask what proportion of words of length ≤ N lies in S and then take the limit of this proportion as N → ∞. If the limit is 1 then S is generic.

An interesting analogy for what we are discussing here is the theory of linear programming. This is a set of ideas, developed more than fifty years ago by George Dantzig, for finding extremals of a set of linear inequalities (equivalently, finding the extreme points of a convex polyhedron). Many scheduling and traffic-control problems may be reduced to linear programming problems. Dantzig's "simplex algorithm" is, in principle of exponential complexity. But these "worst case" problems that are of exponential type almost never occur in practice. In fact Stephen Smale and his group have shown that, in a certain sense, the exceptional problems form a set of measure zero. In other words, in our language, the cases that are of polynomial time are generic. This is the type of result that the AIM workshop on Generic Complexity considered.

In the 1990s, the group theorists---in their study of finitely presented groups---came up with questions similar to the ones discussed here. The techniques developed by the group theorists have turned out to be useful for the cryptographers and vice versa. The Generic Case Complexity workshop had both group theorists and theoretical mathematicians as well as computer scientists.

Quantum computers (which do not exist yet) are a matter of great interest to these theorists. A quantum computer works on an entirely different computing paradigm than the digital computers that we know today. Instead of manipulating bytes, these machines will manipulate Q-bytes. If we can ever build a quantum computer, it will be able to factor a large positive integer of n digits in polynomial-in-log n time. This will in effect put the RSA algorithm (and most other modern cryptographical algorithms) out of business. It happens that there is not much research in the United States on quantum computers, but the Canadians and the British are leading the pack in exploring this fertile new branch of theoretical computer science, physics, and engineering.

There is today a prototype of a quantum computer---that manipulates Q-bits that are much smaller than in the idealized quantum computer that has not yet been built---that can actually perform calculations. The machine fills an entire room, and represents powerful advances in hardware development. It has been used to factor the number 15.

The subject of Generic Case Complexity lies on the cutting edge of theoretical mathematics, theoretical computer science, and quantum physics. It is an exciting frontier in which progress will have immediate impact on the way that we conduct business, and the way that we perform scientific investigations. The group at AIM laid the groundwork for considerable future work in the area.