Counting curves and their projections

被引：16

作者：

Gathen, JV

Karpinski, M

Shparlinski, I

机构：

[1] MACQUARIE UNIV, SCH MATH PHYS COMP & ELECT, N RYDE, NSW 2109, AUSTRALIA

[2] UNIV BONN, DEPT COMP SCI, D-53117 BONN, GERMANY

[3] UNIV TORONTO, DEPT COMP SCI, TORONTO, ON M5S 1A4, CANADA

[4] ETH ZURICH, INST SCI COMPUTAT, ZURICH, SWITZERLAND

[5] INT COMP SCI INST, BERKELEY, CA 94704 USA

来源：

COMPUTATIONAL COMPLEXITY | 1996年 / 6卷 / 01期

关键词：

D O I：

10.1007/BF01202042

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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-comDlete via probabilistic parsimonious Turing reductions.

引用

页码：64 / 99

页数：36

共 46 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[2] Weil bounds for singular curves [J].