• DocumentCode
    939182
  • Title

    Fast evaluation of logarithms in fields of characteristic two

  • Author

    Coppersmith, Don

  • Volume
    30
  • Issue
    4
  • fYear
    1984
  • fDate
    7/1/1984 12:00:00 AM
  • Firstpage
    587
  • Lastpage
    594
  • Abstract
    A method for determining logarithms in GF (2^{n}) is presented. Its asymptotic running time is O(\\exp (cn^{1/3} \\log ^{2/3} n)) for a small constant c , while, by comparison, Adleman\´s scheme runs in time O(\\exp (c^{\´}n^{1/2} \\log ^{1/2} n )) . The ideas give a dramatic improvement even for moderate-sized fields such as GF (2^{127}) , and make (barely) possible computations in fields of size around 2^{400} . The method is not applicable to GF (q) for a large prime q .
  • Keywords
    Cryptography; Galois fields; Logarithmic arithmetic; Communication system security; Cryptography; Galois fields; Graphics; Polynomials; Proposals; Silver;
  • fLanguage
    English
  • Journal_Title
    Information Theory, IEEE Transactions on
  • Publisher
    ieee
  • ISSN
    0018-9448
  • Type

    jour

  • DOI
    10.1109/TIT.1984.1056941
  • Filename
    1056941
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=939182