Title: Fast evaluation of logarithms in fields of characteristic two
Abstract: A method for determining logarithms in GF <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(2^{n})</tex> is presented. Its asymptotic running time is <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(\exp (cn^{1/3} \log^{2/3} n))</tex> for a small constant <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">c</tex> , while, by comparison, Adleman's scheme runs in time <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(\exp (c^{'}n^{1/2} \log^{1/2} n ))</tex> . The ideas give a dramatic improvement even for moderate-sized fields such as GF <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(2^{127})</tex> , and make (barely) possible computations in fields of size around <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2^{400}</tex> . The method is not applicable to GF <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(q)</tex> for a large prime <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</tex> .
Publication Year: 1984
Publication Date: 1984-07-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 306
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot