[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: David A Wagner <[email protected]>, [email protected]*Subject*: Re: Diffie-Hellman in GF(2^n)?*From*: Wei Dai <[email protected]>*Date*: Mon, 13 Nov 1995 12:55:17 -0800 (PST)*In-Reply-To*: <[email protected]>*Sender*: [email protected]

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

**References**:**Re: Diffie-Hellman in GF(2^n)?***From:*Wei Dai <[email protected]>

- Prev by Date:
**"Not the views of my government"** - Next by Date:
**URL Version for ALPHA.C2.ORG FAQ** - Prev by thread:
**Re: Diffie-Hellman in GF(2^n)?** - Next by thread:
**Re: New World Encryption** - Index(es):