"Even adders can multiply using log tables..." PGP is moving to discrete log based cryptography. It will still support RSA, but people will be encouraged to generate discrete log keys. It will use RSA to encrypt to people with RSA keys, and discrete log crypto to encrypt to people with discrete log keys. Many discrete log cryptosystems will be patent free after next year. It may be that they will become more popular over the next few years for that reason. RSA has several more years before its patents expire. Most people are not as familiar with the math behind discrete logs as they are with RSA. The general idea of the difficulty of factoring is pretty easy to understand. It's much easier to multiply two large primes together than to figure out what the primes were just by looking at the result. Discrete logs require a little more explanation. First I am going to write a little bit about the lore of logarithms. I think today a lot of people don't know what they are. When I was a boy, in the 1960's, computers and even calculators were not widely available. Yet engineers in many fields needed to perform calculations. Reaction rates, material strengths, friction, current flow, all such calculations require multiplication and division of numbers with several significant digits. The choices were basically to multiply it out the long way, which was slow, error-prone, and wasteful because it generates twice as many digits as you need; use a slide rule, which usually only gets you two or three digits of accuracy; or to use log tables, which could get you four or five, or sometimes even more, accurate digits. The logarithm of a number is the power that you have to raise some specified base (usually 10 for these purposes) to in order to get that number. The logarithm of 100 base 10 is 2 because 10**2 = 100. The log of 1000 is 3. For numbers not powers of 10, the logarithm has fractional parts. The logarithm of 20 is about 1.3, for example. To multiply two numbers, you find their logs and add them, and then turn the result back into a number. To divide, subtract the logs. So most of the work is just in looking up what the logs are using published tables. Actually we do use logs in a crude form in much of cryptography. Any time you say that the product of two 512 bit numbers is 1024 bits what you mean is that the log base two of the smaller numbers is about 512, and so the log base two of their product is 512+512 or 1024. By the time I was in high school calculators were becoming fairly widespread, but we still learned how to use log tables to do multiplication and division. Whole books were published containing nothing but tables of the logarithms of numbers. You can still find these sometimes in used book stores. There were lots of tricks to using these tables which we had to learn. Logarithms of numbers less than 1 are negative, but the trick was to treat them as the sum of a positive fractional part and a negative integer, so for example the log of .2 was treated as +.3 - 1. This made it easier to look up the values. And there were special sub-tables within the tables to help with interpolating, looking up log values between the entries in the table. Using these you could get more accuracy in your answers. All this was part of the craft of working engineers and scientists of the time. It's hard for people today, raised on throwaway and even virtual calculators, to understand the sense of power that came from using logs for calculations. Until we learned these advanced techniques the only accurate alternatives were the terribly tedious hand methods. Being able to get results by adding up a few numbers from a book was an amazing improvement. The discrete logs used in crypto have very different mathematical properties than regular logarithms, but I thought this bit of history would spark some memories in old-timers and give a new perspective for younger people. Hal