Abstract
Some deterministic and probabilistic methods are presented for counting and estimating the number of points on curves over finite fields, and on their projections. The classical question of estimating the size of the image of a univariate polynomial is a special case. For curves given by sparse polynomials, the counting problem is #P-complete via probabilistic parsimonious Turing reductions.
| Original language | English |
|---|---|
| Pages (from-to) | 64-99 |
| Number of pages | 36 |
| Journal | Computational Complexity |
| Volume | 6 |
| Issue number | 1 |
| Publication status | Published - 1996 |