Several recent preprints have discussed summation polynomial attacks on the ECDLP in characteristic 2:

- eprint 2015/310, New algorithm for the discrete logarithm problem on elliptic curves, by Igor Semaev.
- eprint 2015/319, Point Decomposition Problem in Binary Elliptic Curves, by Koray Karabina.
- arxiv 1503.08001, Notes on summation polynomials, by Michiel Kosters and Sze Ling Yeo.

To recall some history, in 2004 Semaev introduced a fundamental new idea for index calculus algorithms for the ECDLP. Fix an elliptic curve $latex E$ over a field $latex K$. Semaev’s summation polynomials $latex S_m( x_1, dots, x_m )$ have the property that if $latex S_m( a_1, dots, a_m ) = 0$ for some field elements $latex a_1, dots, a_m in K$ then there are elliptic curve points $latex (a_1, b_1), dots, (a_m,b_m)$ on $latex E(overline{K})$ such that $latex (a_1, b_1) + cdots + (a_m,b_m) = 0$.

Gaudry and Diem explored how to…

View original post 1,278 more words