[43317] in Cypherpunks
Re: Diffie-Hellman in GF(2^n)?
daemon@ATHENA.MIT.EDU (Wei Dai)
Mon Nov 13 02:37:57 1995
Date: Sun, 12 Nov 1995 23:29:57 -0800 (PST)
From: Wei Dai <weidai@eskimo.com>
To: David A Wagner <daw@CS.Berkeley.EDU>
Cc: cypherpunks@toad.com
In-Reply-To: <199511122243.OAA18565@delhi.CS.Berkeley.EDU>
> 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
