Finding Points on Curves over Finite Fields
Joachim von zur Gathen, Igor E. Shparlinski, Alistair Sinclair · SIAM Journal on Computing · 2003
We solve two computational problems concerning plane algebraic curves over finite fields: generating a uniformly random point, and finding all points deterministically in amortized polynomial time (over a prime field, for nonexceptional curves).