RE: Discrete logs 1

17 Dec 2003

      [...Interesting discussion of logarithms deleted...]
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

As an apparent old-timer (calculators weren't common until my college days, 
which puts me a couple of years before you, I guess) I enjoyed the 
retrospective, and I even recall the joke that goes with the punchline you 
quoted.  It's amazing to realize that only a few years ago, we were 
calculating orbital trajectories using logarithms by lining up marks on 
little sticks of wood!  I have to admit, though, that I was a little 
disappointed after your opening paragraph, because what I was really hoping 
to hear was a straightforward explanation of discrete logs, which, as you 
say, are entirely different.  A simple layman's explanation of what they 
are and how they're useful in crypto would be nice, especially since PGP is 
moving toward this (just when I was beginning to get a handle on RSA!).

Now that I have an interest in all this, I wish Rich Schroeppel still 
worked here (he worked at Inference when I started here in '88, and has 
since done a lot of pioneering work on discrete logs).  Me, I'm still 
trying to figure out what sort of seed is best to plant in a Galois 
field...

Tunny
======================================================================
 James A. Tunnicliffe   | WWWeb: http://www.inference.com/~tunny
 Inference Corporation  | PGP Fingerprint:   CA 23 E2 F3 AC 2D 0C 77
 tunny@Inference.com    |                    36 07 D9 33 3D 32 53 9C
======================================================================

begin 600 WINMAIL.DAT
M>)\^(@T/`0:0" `$```````!``$``0>0!@`(````Y 0```````#H``$(@ <`
M& ```$E032Y-:6-R;W-O9G0@36%I;"Y.;W1E`#$(`06 `P`.````S <+``$`
M!P`H``L`!0`>`0$@@ ,`#@```,P'"P`!``<`* `,``4`'P$!"8 !`"$```!#
M-#$W,#$T0T8Q,S-$,#$Q.3,P03 P04$P,$$U1C8P1 #O!@$-@ 0``@````(`
M`@`!!( !`!0```!213H@1&ES8W)E=&4@;&]G<R Q`$H&`0.0!@!T" ``&@``
M``,`)@```````P`V```````>`' ``0```! ```!$:7-C<F5T92!L;V=S(#$`
M`@%Q``$````;`````;O'F<4U)C98U#*Q$="3"@"J`*7V#0`;.WUC``,`+@``
M`````P`&$'M@494#``<0:04``!X`"! !````90```$E.5$5215-424Y'1$E3
M0U534TE/3D]&3$]'05))5$A-4T1%3$5414142$5$25-#4D5414Q/1U-54T5$
M24Y#4EE05$](059%5D52641)1D9%4D5.5$U!5$A%34%424-!3%!23U `````
M`P`0$ 0````#`!$0``````(!"1 !````:@4``&8%``!_" ``3%I&=7AM`T?_
M``H!#P(5`J0#Y 7K`H,`4!,#5 (`8V@*P'-E=.XR!@`&PP*#,@/&!Q,"@P8S
M!$8"`'!R<3$@UPA5![("@S03#7T*@ C/Q0G9.Q?_,C4U`H *@8,-L0M@;F<Q
M,#,4(.$+`VQI,S8-\ M5%B)%# %C`$ @6RX=4$D7`C $D >0= N 9R!D*00`
M8W4$$&D"("!O%&8@%Y!G"L!I=&AV;00@#;!L$@`)@!U175\*APMD$O(,`130
M;QV@8_$%0%1H91XS& `=H!\25P0@'H )@" +@" %`'GI!3!O(!' =B* )) D
M$&\>,0W0';$"," `P!^ 9;DEL6EC!T *A2'A< 20GQWP!Y$?@ .1& !G=0M@
M0P7 'R@L(&)U!4!)\R>!"&!G: 5 'X $`"D0OQ]P'N(J$21 )! *A7<(8.IL
M([!S"K%K*_ #<"* /P> !& (@00@(]$&\&0M-QWP!X 1X" `<".P9VGQ))%A
M(&X'T2<1+ `B(>LN<@(0<@J%>0A@&P`5<;<G$"<`'_ N"H4*A4@F5[\;;Q0#
M"_$QQ@K[')E!+@*=+A!P-+$E<BUW("@F0:\>< M@*O$$('<E4B<%0'T%H&T$
M8 .@,) =\ ,@;9\D\!=Q'_ PL!XP87DH\?YW*A 1L";0*3 $("R!+K#-!:!U
M,2$>XGEE$=$I$/\-P 6P(H P<2D`*6 H``>0S',I*5$)\&IO/- CL/LET2?1
M= -@+T8I`"XB/H&_)) GPB9!`R _(C[ :R* \R>1!4!G;P>1`_ ?@#\3/3N0
M;A&P&\ NT#!B('&6=2(!(# @*5!T)RX!/0# >AX")$$8``= :7K[0>4"(&PD
M\"ZP)4 'X#S4_F%"4#L1(H XTB/P."4>`H\%L"I1!T G@')A:B(A[RSD'H >
M`A\I8B3P0X$>`O\\4"6A+# $(![!&\ "0#QQO1WA8TQR'P`KH 1P(42!XR1D
M)$%A9&T?<"D`*83G3T)"(2E@=V$N`4S&'D']-M%O"X @$2X0`8 5<3!QOP7 
M)P%+PS2Q1X!)H'!/L?\],"9 (X$[(5 '1:)&D2F0?G!%-2)P*W)08QW@2:!I
M7RG!+]%04 L@/I!X"U%N_R81'L0BJSL50#$$($/244#N>4 Q/7$E<6D8`$:1
M)1?]1'%!*_ '<#QB"V &P !P_T3!5\U44R711J$]<2XB*9#;!^!>PB<]<2.!
M9B@0(\G_*Z0],"[ )C! (0>0+U$',8=&D4IQ8A @4$=0(\ Y.\%O=D4T5W,J
M`RAJ?QZ !4 [,$#14#0],"Y@;K]+PR1!,+ %0"ZP)Z%D/')!`Z!24T$A*3%=
M3O]?HU #)',#D5&2'<(CPD$TKP0`/=(#\3MP4CM24Q&P_0-@93;@'^!-,D%!
M*Z L,'<CH2)P/7$H(G%MA5 ";O\E0V,Q964=X K 4;)M\R/1>"<X.$ T$< $
M(&,$9/\"("Z2%Y J<U60<G$&<1X17VV"3)(BJV@@1(!-0"%)K"=M;14_@'E%
M-697`/\(<#R!*3%44RQ@`" >XA'P/R.B/1)E,21!5^)JQ"!'?P= 48 $('<`
M'^ @,C%L5/4PD&XK)CU\SWW??N]__[(]-(4@2D3P!Y%!1' ?? (F,!O )3%$
M@"!\(&)7@S!E8CHD8 ) <- Z+R]WA! N"X!O1>(N.5$O?G1\&6\9"%"^<E%P
M2:!8,X,!8V)&'@%?!) 4T%&1@X!$@$-<8#(H,R!%$B!&B1!!0Y&(\$0@,(F@
M-S>!)OV%0T!O)X3B@N&#`8Q/1(##&^")X#<@1#F-<(D0*C.)T#,2(#6)$#E#
M?WQ?C_^1#Y(?@)XTA1<A``&4X ``0 `Y`)!VJ_<*R+L!`P#Q/PD$```"`4<`
M`0```#$```!C/553.V$](#MP/4EN9F5R96YC93ML/4Q!3D1252TY-C$Q,#$Q
M-30P,3%:+3DR-#4``````@'Y/P$```!*`````````-RG0,C 0A :M+D(`"LO
MX8(!`````````"]//4E.1D5214Y#12]/53U.3U9!5$\O0TX]4D5#25!)14Y4
M4R]#3CU454Y.60```!X`^#\!````%0```$IA;65S($$N(%1U;FYI8VQI9F9E
M``````(!^S\!````2@````````#<IT#(P$(0&K2Y" `K+^&"`0`````````O
M3SU)3D9%4D5.0T4O3U4]3D]6051/+T-./5)%0TE0245.5%,O0TX]5%5.3ED`
M```>`/H_`0```!4```!*86UE<R!!+B!4=6YN:6-L:69F90````! ``<PX,:E
M>@G(NP% ``@PL&T6^ K(NP$#``TT_3\```(!%#0!````$ ```%24H< I?Q ;
MI8<(`"LJ)1<>`#T``0````4```!213H@``````L`*0``````"P`C```````"
M`7\``0```% ````\8SU54R5A/5\E<#U);F9E<F5N8V4E;#U,04Y$4E4M.38Q
M,3 Q,34T,#$Q6BTY,C0U0&QA;F1R=2YN;W9A=&\N:6YF97)E;F-E,BYC;VT^
#`+)S
`
end