From: Wei Dai <weidai@eskimo.com>
Date: Tue, 14 Nov 1995 05:26:24 +0800
To: David A Wagner <cypherpunks@toad.com
Subject: Re: Diffie-Hellman in GF(2^n)?
In-Reply-To: <Pine.SUN.3.91.951112224949.24714A-100000@eskimo.com>
Message-ID: <Pine.SUN.3.91.951113123310.24760A-100000@eskimo.com>
MIME-Version: 1.0
Content-Type: text/plain


I wrote earlier:

> Thanks for the reference.  The paper gives a running time of exp(c(n 
> log n)^(1/2)) for discrete log in GF(p) and exp(c*n^(1/3)*(log n)^(2/3)) 
> for discrete log in GF(2^n).  However, this paper was published in 1985. 
> There is now an algorithm to calculate discrete logs in GF(p) in
> exp(c*n^(1/3)*(log n)^(2/3)) (see prime.discrete.logs.ps.Z in the same
> directory), so perhaps GF(2^n) isn't so bad after all. 

To clarify my earlier post, although both of the latter two algorithms
have a runtime of the form exp(c*n^(1/3)*(log n)^(2/3)), for GF(p)
c=1.922+o(1), for GF(2^n) c=1.405+o(1).  This seems to imply that if 
GF(2^n) is to be used, n needs to be 2.56*log p to achieve a comparable 
level of security to using GF(p).  (2.56=1.922^3/1.405^3)

Wei Dai