Paper 2014/806

Summation polynomial algorithms for elliptic curves in characteristic two

Steven D. Galbraith and Shishay W. Gebregiyorgis


The paper is about the discrete logarithm problem for elliptic curves over characteristic 2 finite fields F_2^n of prime degree n. We consider practical issues about index calculus attacks using summation polynomials in this setting. The contributions of the paper include: a choice of variables for binary Edwards curves (invariant under the action of a relatively large group) to lower the degree of the summation polynomials; a choice of factor base that “breaks symmetry” and increases the probability of finding a relation; an experimental investigation of the use of SAT solvers rather than Gröbner basis methods for solving multivariate polynomial equations over F2. We show that our choice of variables gives a significant improvement to previous work in this case. The symmetry breaking factor base and use of SAT solvers seem to give some benefits in practice, but our experimental results are not conclusive. Our work indicates that Pollard rho is still much faster than index calculus algorithms for the ECDLP (and even for variants such as the oracle-assisted static Diffie-Hellman problem of Granger and Joux-Vitse) over prime extension fields F_2^n of reasonable size.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Major revision. INDOCRYPT 2014
Contact author(s)
bonjour mit @ gmail com
2014-10-15: revised
2014-10-11: received
See all versions
Short URL
Creative Commons Attribution


      author = {Steven D.  Galbraith and Shishay W.  Gebregiyorgis},
      title = {Summation polynomial algorithms for elliptic curves in characteristic two},
      howpublished = {Cryptology ePrint Archive, Paper 2014/806},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.