
"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

At 9:16 AM -0800 10/31/96, Hal Finney wrote:
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 ... 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
(These were the "Smoley" books, amongst others.) Sliderules were just becoming common when I was in high school.... Seriously, only a very few of us had and used sliderules...mine was a big synthetic K & E (Keuffel and Esser, as I recall). The raging "DOS vs. Mac" or "RISC vs. CISC" debate of that age was "aluminum" (the yellow Dietzgens) vs. the old standby, "bamboo." Plus some oddball circular sliderules. Those of us who used sliderules were sometimes characterized as "nerds"...perhaps this is why I today have such a strong reation to so many young programmers and engineers voluntarily calling themselves "nerds" and "geeks." (The deconstructive, postmodern theory is presumably that they are "reclaiming" the term, as with dykes and niggers reclaiming those hateful terms. I still reject this as crap.)
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.
And these tables were of course a major motivation for the development of computers, going back centuries. Mechanical computation of log tables, and even Babbage's work, was inspired by this. Ditto for artillery range tables, some of the earliest applications of the earliest digital computers. (Precomputation of values, aka "tabling," is of course still a modern topic. Some of the newer names come out of AI, compiler research, etc. For example, speculative execution. Not exactly a book of precomputed logs, but similar.) Recall that Fermi, von Neumann, and Feynman had a contest at Los Alamos in WWII, with some problem being computed by Fermi on sliderule, von Neumann on early versions of computers, and Feynman with log tables and adding machines. Feynman won, as I recall the story, but presumably only because von Neumann was not allowed to do it in his head. (The funny story goes that a problem was going around Los Alamos that goes like this: two trains are approaching each other on the same track, one train going 60 mph and the other going 40 mph. When the trains are 100 miles apart, a fly takes off from one train and flies 200 mph toward the other train, then turns around and flies back at the same speed, and so on, until the trains collide. How far does he fly? Von Neumann was asked this, glanced at the ceiling, and gave the answer (left as an exercise for the reader). The questioner said, "Oh, Dr. von Neumann, I'm glad you saw the trick and didn't try to compute the infinite series." Von Neumann replied, "You mean there's another way?") --Tim May "The government announcement is disastrous," said Jim Bidzos,.."We warned IBM that the National Security Agency would try to twist their technology." [NYT, 1996-10-02] We got computers, we're tapping phone lines, I know that that ain't allowed. ---------:---------:---------:---------:---------:---------:---------:---- Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay@got.net 408-728-0152 | anonymous networks, digital pseudonyms, zero W.A.S.T.E.: Corralitos, CA | knowledge, reputations, information markets, Higher Power: 2^1,257,787-1 | black markets, collapse of governments. "National borders aren't even speed bumps on the information superhighway."

-----BEGIN PGP SIGNED MESSAGE----- "Timothy C. May" <tcmay@got.net> writes:
At 9:16 AM -0800 10/31/96, Hal Finney wrote: <snip> Sliderules were just becoming common when I was in high school....
Seriously, only a very few of us had and used sliderules...mine was a big synthetic K & E (Keuffel and Esser, as I recall). The raging "DOS vs. Mac" or "RISC vs. CISC" debate of that age was "aluminum" (the yellow Dietzgens) vs. the old standby, "bamboo." Plus some oddball circular sliderules.
Those of us who used sliderules were sometimes characterized as "nerds"...perhaps this is why I today have such a strong reation to so many young programmers and engineers voluntarily calling themselves "nerds" and "geeks." (The deconstructive, postmodern theory is presumably that they are "reclaiming" the term, as with dykes and niggers reclaiming those hateful terms. I still reject this as crap.)
What's there to reject in "Yeah, I'm happy with what I want, so fuck you?" (Which is essentially what this reclaming stuff is). Of course, I see nothing wrong with rejecting postmodernist intellectuals :-) but they have stolen some good ideas. <comments re: tables snipped>
(Precomputation of values, aka "tabling," is of course still a modern topic. Some of the newer names come out of AI, compiler research, etc. For example, speculative execution. Not exactly a book of precomputed logs, but similar.)
Let's not forget memoizing, either. Kinda space ineficient, but with a decent virtual memory system you can cache perviously-used solutions and go real fast. Hmmm, like, say you were for some reason trying to factor a multitude of large composites. Precomputing everything would probably be rather inefficient, but once you've factords something, why throw it away? (I knew there would be some crypto relevance in here :-) Jer "standing on top of the world/ never knew how you never could/ never knew why you never could live/ innocent life that everyone did" -Wormhole -----BEGIN PGP SIGNATURE----- Version: 2.6.2 iQB1AwUBMnpjBckz/YzIV3P5AQEpWgMAl8PkPlrY/s84JGnuoiX7gPXMfjQlo+fZ tBxJVg6FP9EVB5ASL2FDk3s8butKC6FP7SpJZOSzmUSExawzFpuHW1IZc5efxhBR Cyzjj1ybUhEUGPHlBhrqbTXU5EzI5iB5 =m5oK -----END PGP SIGNATURE-----
participants (3)
-
Hal Finney
-
Jeremiah A Blatz
-
Timothy C. May