Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Zech's logarithm
open-in-new
<h2 id="definition">Definition</h2> <p>Given a <a href="/facts/Primitive_element_(finite_field)/JNGL1jQq">primitive element</a> α {\displaystyle \alpha } of a finite field, the Zech logarithm relative to the base α {\displaystyle \alpha } is defined by the equation </p> α Z α ( n ) = 1 + α n , {\displaystyle \alpha ^{Z_{\alpha }(n)}=1+\alpha ^{n},} <p>which is often rewritten as </p> Z α ( n ) = log α ( 1 + α n ) . {\displaystyle Z_{\alpha }(n)=\log _{\alpha }(1+\alpha ^{n}).} <p>The choice of base α {\displaystyle \alpha } is usually dropped from the notation when it is clear from the context. </p><p>To be more precise, Z α {\displaystyle Z_{\alpha }} is a <a href="/facts/Function_(mathematics)/CdReEKCh">function</a> on the <a href="/facts/Integer/PUwwrawx">integers</a> <a href="/facts/Modular_arithmetic/0wtRa5dU">modulo</a> the multiplicative order of α {\displaystyle \alpha } , and takes values in the same set. In order to describe every element, it is convenient to formally add a new symbol − ∞ {\displaystyle -\infty } , along with the definitions </p> α − ∞ = 0 {\displaystyle \alpha ^{-\infty }=0} n + ( − ∞ ) = − ∞ {\displaystyle n+(-\infty )=-\infty } Z α ( − ∞ ) = 0 {\displaystyle Z_{\alpha }(-\infty )=0} Z α ( e ) = − ∞ {\displaystyle Z_{\alpha }(e)=-\infty } <p>where e {\displaystyle e} is an integer satisfying α e = − 1 {\displaystyle \alpha ^{e}=-1} , that is e = 0 {\displaystyle e=0} for a <a href="/facts/Field_(mathematics)/xAjAS4ko">field</a> of <a href="/facts/Characteristic_(algebra)/D2VzcQaG">characteristic</a> 2, and e = q − 1 2 {\displaystyle e={\frac {q-1}{2}}} for a field of <a href="/facts/Parity_(mathematics)/7zq2UM4V">odd</a> characteristic with q {\displaystyle q} elements. </p><p>Using the Zech logarithm, finite field arithmetic can be done in the exponential representation: </p> α m + α n = α m ⋅ ( 1 + α n − m ) = α m ⋅ α Z ( n − m ) = α m + Z ( n − m ) {\displaystyle \alpha ^{m}+\alpha ^{n}=\alpha ^{m}\cdot (1+\alpha ^{n-m})=\alpha ^{m}\cdot \alpha ^{Z(n-m)}=\alpha ^{m+Z(n-m)}} − α n = ( − 1 ) ⋅ α n = α e ⋅ α n = α e + n {\displaystyle -\alpha ^{n}=(-1)\cdot \alpha ^{n}=\alpha ^{e}\cdot \alpha ^{n}=\alpha ^{e+n}} α m − α n = α m + ( − α n ) = α m + Z ( e + n − m ) {\displaystyle \alpha ^{m}-\alpha ^{n}=\alpha ^{m}+(-\alpha ^{n})=\alpha ^{m+Z(e+n-m)}} α m ⋅ α n = α m + n {\displaystyle \alpha ^{m}\cdot \alpha ^{n}=\alpha ^{m+n}} ( α m ) − 1 = α − m {\displaystyle \left(\alpha ^{m}\right)^{-1}=\alpha ^{-m}} α m / α n = α m ⋅ ( α n ) − 1 = α m − n {\displaystyle \alpha ^{m}/\alpha ^{n}=\alpha ^{m}\cdot \left(\alpha ^{n}\right)^{-1}=\alpha ^{m-n}} <p>These formulas remain true with our conventions with the symbol − ∞ {\displaystyle -\infty } , with the caveat that subtraction of − ∞ {\displaystyle -\infty } is undefined. In particular, the addition and subtraction formulas need to treat m = − ∞ {\displaystyle m=-\infty } as a special case. </p><p>This can be extended to arithmetic of the <a href="/facts/Projective_line/PhRgf87G">projective line</a> by introducing another symbol + ∞ {\displaystyle +\infty } satisfying α + ∞ = ∞ {\displaystyle \alpha ^{+\infty }=\infty } and other rules as appropriate. </p><p>For fields of characteristic 2, </p> Z α ( n ) = m ⟺ Z α ( m ) = n {\displaystyle Z_{\alpha }(n)=m\iff Z_{\alpha }(m)=n} . <h2 id="uses">Uses</h2> <p>For sufficiently small finite fields, a table of Zech logarithms allows an especially efficient implementation of all finite field arithmetic in terms of a small number of integer addition/subtractions and table look-ups. </p><p>The utility of this method diminishes for large fields where one cannot efficiently store the table. This method is also inefficient when doing very few operations in the finite field, because one spends more time computing the table than one does in actual calculation. </p> <h2 id="examples">Examples</h2> <p>Let <i>α</i> ∈ GF(23) be a <a href="/facts/Root_of_a_polynomial/mlK3dhoT">root</a> of the <a href="/facts/Primitive_polynomial_(field_theory)/8nvXpBUL">primitive polynomial</a> <i>x</i>3 + <i>x</i>2 + 1. The traditional representation of elements of this field is as <a href="/facts/Polynomial/Lzak8VVx">polynomials</a> in α of <a href="/facts/Degree_of_a_polynomial/Bf8vEIhf">degree</a> 2 or less. </p><p>A table of Zech logarithms for this field are <i>Z</i>(−∞) = 0, <i>Z</i>(0) = −∞, <i>Z</i>(1) = 5, <i>Z</i>(2) = 3, <i>Z</i>(3) = 2, <i>Z</i>(4) = 6, <i>Z</i>(5) = 1, and <i>Z</i>(6) = 4. The multiplicative order of <i>α</i> is 7, so the exponential representation works with integers modulo 7. </p><p>Since <i>α</i> is a root of <i>x</i>3 + <i>x</i>2 + 1 then that means <i>α</i>3 + <i>α</i>2 + 1 = 0, or if we recall that since all coefficients are in GF(2), subtraction is the same as addition, we obtain <i>α</i>3 = <i>α</i>2 + 1. </p><p>The conversion from exponential to polynomial representations is given by </p> α 3 = α 2 + 1 {\displaystyle \alpha ^{3}=\alpha ^{2}+1} (as shown above) α 4 = α 3 α = ( α 2 + 1 ) α = α 3 + α = α 2 + α + 1 {\displaystyle \alpha ^{4}=\alpha ^{3}\alpha =(\alpha ^{2}+1)\alpha =\alpha ^{3}+\alpha =\alpha ^{2}+\alpha +1} α 5 = α 4 α = ( α 2 + α + 1 ) α = α 3 + α 2 + α = α 2 + 1 + α 2 + α = α + 1 {\displaystyle \alpha ^{5}=\alpha ^{4}\alpha =(\alpha ^{2}+\alpha +1)\alpha =\alpha ^{3}+\alpha ^{2}+\alpha =\alpha ^{2}+1+\alpha ^{2}+\alpha =\alpha +1} α 6 = α 5 α = ( α + 1 ) α = α 2 + α {\displaystyle \alpha ^{6}=\alpha ^{5}\alpha =(\alpha +1)\alpha =\alpha ^{2}+\alpha } <p>Using Zech logarithms to compute <i>α</i> 6 + <i>α</i> 3: </p> α 6 + α 3 = α 6 + Z ( − 3 ) = α 6 + Z ( 4 ) = α 6 + 6 = α 12 = α 5 , {\displaystyle \alpha ^{6}+\alpha ^{3}=\alpha ^{6+Z(-3)}=\alpha ^{6+Z(4)}=\alpha ^{6+6}=\alpha ^{12}=\alpha ^{5},} <p>or, more efficiently, </p> α 6 + α 3 = α 3 + Z ( 3 ) = α 3 + 2 = α 5 , {\displaystyle \alpha ^{6}+\alpha ^{3}=\alpha ^{3+Z(3)}=\alpha ^{3+2}=\alpha ^{5},} <p>and verifying it in the polynomial representation: </p> α 6 + α 3 = ( α 2 + α ) + ( α 2 + 1 ) = α + 1 = α 5 . {\displaystyle \alpha ^{6}+\alpha ^{3}=(\alpha ^{2}+\alpha )+(\alpha ^{2}+1)=\alpha +1=\alpha ^{5}.} <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Gaussian_logarithm/FUTC5nxl">Gaussian logarithm</a></li> <li><a href="/facts/Irish_logarithm/dnyJulkX">Irish logarithm</a>, a similar technique derived empirically by Percy Ludgate</li> <li><a href="/facts/Finite_field_arithmetic/yuG8TYy5">Finite field arithmetic</a></li> <li><a href="/facts/Logarithm_table/q6EhDnWk">Logarithm table</a></li></ul> <h2 id="further-reading">Further reading</h2> <ul><li>Fletcher, Alan; <a href="/facts/Jeffrey_Charles_Percy_Miller/wPxXrRDR">Miller, Jeffrey Charles Percy</a>; <a href="/facts/Louis_Rosenhead/NPewuIpW">Rosenhead, Louis</a> (1946) [1943]. <i>An Index of Mathematical Tables</i> (1 ed.). <a href="/facts/Blackwell_Scientific_Publications_Ltd./XUkBW8kE">Blackwell Scientific Publications Ltd.</a>, Oxford / <a href="/facts/McGraw-Hill/oG8VpKJT">McGraw-Hill</a>, New York.</li> <li><a href="/facts/John_Horton_Conway/g3PA1zoK">Conway, John Horton</a> (1968). Churchhouse, Robert F.; Herz, J.-C. (eds.). "A tabulation of some information concerning finite fields". <i>Computers in Mathematical Research</i>. Amsterdam: <a href="/facts/North-Holland_Publishing_Company/jkPSAEmR">North-Holland Publishing Company</a>: 37–50. <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0237467">0237467</a>.</li> <li><a href="/facts/Clement_Wing_Hong_Lam/M5T0dTYq">Lam, Clement Wing Hong</a>; <a href="/facts/John_K._S._McKay/hsoKmmMF">McKay, John K. S.</a> (1973-11-01). <a href="https://doi.org/10.1145%2F355611.362544">"Algorithm 469: Arithmetic over a finite field [A1]"</a>. <i><a href="/facts/Communications_of_the_ACM/Ix1DvEAk">Communications of the ACM</a></i>. Collected Algorithms of the ACM (CALGO). 16 (11). <a href="/facts/Association_for_Computing_Machinery/abI2atlP">Association for Computing Machinery</a> (ACM): 699. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F355611.362544">10.1145/355611.362544</a>. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0001-0782">0001-0782</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:62794130">62794130</a>. toms/469. <a href="http://www.acm.org/calgo/">[1]</a> <a href="https://people.sc.fsu.edu/~jburkardt/html/toms.html">[2]</a> <a href="http://www.netlib.org/toms-2014-06-10/620">[3]</a></li> <li>Kühn, Klaus (2008). <a href="http://www.rechenschieber.org/Gauss.pdf">"C. F. Gauß und die Logarithmen"</a> (PDF) (in German). Alling-Biburg, Germany. <a href="https://web.archive.org/web/20180714030921/http://www.rechenschieber.org/Gauss.pdf">Archived</a> (PDF) from the original on 2018-07-14. Retrieved 2018-07-14.</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Zech, Julius August Christoph (1849). Tafeln der Additions- und Subtractions-Logarithmen für sieben Stellen (in German) (Specially reprinted (from Vega–Hülße collection) 1st ed.). Leipzig: Weidmann'sche Buchhandlung. Archived from the original on 2018-07-14. Retrieved 2018-07-14. Also part of: Freiherr von Vega, Georg (1849). Hülße, Julius Ambrosius [in German]; Zech, Julius August Christoph (eds.). Sammlung mathematischer Tafeln (in German) (Completely reworked ed.). Leipzig: Weidmann'sche Buchhandlung. Bibcode:1849smt..book.....V. Archived from the original on 2018-07-14. Retrieved 2018-07-14. <a href="/wiki/Julius_August_Christoph_Zech" target="_blank">/wiki/Julius_August_Christoph_Zech</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Zech, Julius August Christoph (1863) [1849]. Tafeln der Additions- und Subtractions-Logarithmen für sieben Stellen (in German) (Specially reprinted (from Vega–Hülße collection) 2nd ed.). Berlin: Weidmann'sche Buchhandlung. Archived from the original on 2018-07-14. Retrieved 2018-07-13. <a href="/wiki/Julius_August_Christoph_Zech" target="_blank">/wiki/Julius_August_Christoph_Zech</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Zech, Julius August Christoph (1892) [1849]. Tafeln der Additions- und Subtractions-Logarithmen für sieben Stellen (in German) (Specially reprinted (from Vega–Hülße collection) 3rd ed.). Berlin: Weidmann'sche Buchhandlung. Archived from the original on 2018-07-14. Retrieved 2018-07-13. <a href="/wiki/Julius_August_Christoph_Zech" target="_blank">/wiki/Julius_August_Christoph_Zech</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Zech, Julius August Christoph (1910) [1849]. Tafeln der Additions- und Subtractions-Logarithmen für sieben Stellen (in German) (Specially reprinted (from Vega–Hülße collection) 4th ed.). Berlin: Weidmann'sche Buchhandlung. Archived from the original on 2018-07-14. Retrieved 2018-07-13. <a href="/wiki/Julius_August_Christoph_Zech" target="_blank">/wiki/Julius_August_Christoph_Zech</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Lidl, Rudolf; Niederreiter, Harald (1997). Finite Fields (2nd ed.). Cambridge University Press. ISBN 978-0-521-39231-0. <a href="978-0-521-39231-0" target="_blank">978-0-521-39231-0</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Jacoby, Carl Gustav Jacob (1846). "Über die Kreistheilung und ihre Anwendung auf die Zahlentheorie". Journal für die reine und angewandte Mathematik (in German). 1846 (30): 166–182. doi:10.1515/crll.1846.30.166. ISSN 0075-4102. S2CID 120615565. (NB. Also part of "Gesammelte Werke", Volume 6, pages 254–274.) <a href="/wiki/Carl_Gustav_Jacob_Jacobi" target="_blank">/wiki/Carl_Gustav_Jacob_Jacobi</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> </ol>