Modular counting of rational points over finite fields

被引：14

作者：

Wan, Daqing ^{[1
]}

机构：

[1] Univ Calif Irvine, Dept Math, Irvine, CA 92697 USA

来源：

FOUNDATIONS OF COMPUTATIONAL MATHEMATICS | 2008年 / 8卷 / 05期

关键词：

p-adic modular counting of rational points; sparse polynomials over finite fields; Stickelberger theorem; Gross-Koblitz formula;

D O I：

10.1007/s10208-007-0245-y

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Let F-q be the finite field of q elements, where q = p(h). Let f(x) be a polynomial over F-q in n variables with m nonzero terms. Let N(f) denote the number of solutions of f(x) = 0 with coordinates in F-q. In this paper we give a deterministic algorithm which computes the reduction of N(f) modulo p(b) in O(n(8m)((h+b)p)) bit operations. This is singly exponential in each of the parameters {h, b, p}, answering affirmatively an open problem proposed by Gopalan, Guruswami, and Lipton.

引用

页码：597 / 605

页数：9

共 13 条

[1]

Beigel R., 1994, Computational Complexity, V4, P350, DOI 10.1007/BF01263423

[2]

Copalan P, 2006, LECT NOTES COMPUT SC, V3887, P544

[3]

EHRENFEUCHT A, 1990, 8543CS ICSI

[4] Counting curves and their projections [J].