1995-11-13 - Re: Diffie-Hellman in GF(2^n)?

Header Data

From: Wei Dai <weidai@eskimo.com>
To: David A Wagner <daw@CS.Berkeley.EDU>
Message Hash: d7baf25784a939f49403592ff17cf63a8b3eb95f02522df0031e71598fa86677
Message ID: <Pine.SUN.3.91.951112224949.24714A-100000@eskimo.com>
Reply To: <199511122243.OAA18565@delhi.CS.Berkeley.EDU>
UTC Datetime: 1995-11-13 07:48:34 UTC
Raw Date: Mon, 13 Nov 1995 15:48:34 +0800

Raw message

From: Wei Dai <weidai@eskimo.com>
Date: Mon, 13 Nov 1995 15:48:34 +0800
To: David A Wagner <daw@CS.Berkeley.EDU>
Subject: Re: Diffie-Hellman in GF(2^n)?
In-Reply-To: <199511122243.OAA18565@delhi.CS.Berkeley.EDU>
Message-ID: <Pine.SUN.3.91.951112224949.24714A-100000@eskimo.com>
MIME-Version: 1.0
Content-Type: text/plain


> I don't know enough about number theory to judge for myself;
> but you can read the (long) paper yourself at
> 
> 	ftp://netlib.att.com/netlib/att/math/odlyzko/discrete.logs.ps.Z

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. 

Wei Dai





Thread