Séminaire de Cryptographie

Accueil     Présentation     Archives

Christiaan van de Woestijne

Deterministic equation solving over finite fields

It is a curious fact that most efficient algorithms for solving algebraic equations over finite fields are probabilistic. In this talk, I will give an overview over deterministic techniques that are applicable. The case of constructing rational points on elliptic curves is especially relevant for cryptographic applications. I will give a detailed exposition of my algorithm for this purpose and also discuss the complexity from various viewpoints.