Abelian surfaces with a given number of points

Опубликовано 6 сентября 2016, 18:55

This is a report on joint work with Everett Howe and Kristin Lauter. I will discuss the genus 2 analogue of the problem of efficiently constructing an elliptic curve over a finite field with a prescribed number N of points. If N is provided with its prime factorization, the elliptic construction I gave with Broker is heuristically polynomial time outside a zero density subset of input values N. I will explain why the analogous construction to obtain abelian surfaces of given order N is intrinsically exponential.