Jeudi 4 juin 2009, à 14h30 en C048.
Thomas Icart (Sagem).
How to Hash onto Elliptic Curves.

We describe the first algorithm that given an elliptic curve E defined over Fq, maps elements of Fq onto E in deterministic polynomial time and in a constant number of operations over Fq. The algorithm is based on computing a cube root and is different from the classical probabilistic `try-and-increment' method. As an application we show how to hash deterministically onto an elliptic curve, an operation that was until now known possible only on a special class of supersingular curves.