Discrete logs 1

"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-----