{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T16:14:33Z","timestamp":1775060073174,"version":"3.50.1"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1996,3,1]],"date-time":"1996-03-01T00:00:00Z","timestamp":825638400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Comput Complexity"],"published-print":{"date-parts":[[1996,3]]},"DOI":"10.1007\/bf01202042","type":"journal-article","created":{"date-parts":[[2005,2,26]],"date-time":"2005-02-26T15:44:09Z","timestamp":1109432649000},"page":"64-99","source":"Crossref","is-referenced-by-count":28,"title":["Counting curves and their projections"],"prefix":"10.1007","volume":"6","author":[{"given":"Joachim","family":"von zur Gathen","sequence":"first","affiliation":[]},{"given":"Marek","family":"Karpinski","sequence":"additional","affiliation":[]},{"given":"Igor","family":"Shparlinski","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"703","DOI":"10.2307\/2118576","volume":"140","author":"W. R. Alford","year":"1994","unstructured":"W. R. Alford, A. Granville, andC. Pomerance, There are infinitely many Carmichael numbers.Annals of Mathematics 140 (1994), 703?722.","journal-title":"Annals of Mathematics"},{"key":"CR2","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1007\/BF01195534","volume":"7","author":"E. Bach","year":"1996","unstructured":"E. Bach, Weil bounds for singular curves.Applicable algebra in Engineering, Communication and Computing 7 (1996), 289?298.","journal-title":"Applicable algebra in Engineering, Communication and Computing"},{"key":"CR3","doi-asserted-by":"crossref","first-page":"417","DOI":"10.4064\/aa-5-4-417-423","volume":"5","author":"J. Birch","year":"1959","unstructured":"J. Birch andH. P. F. Swinnerton-Dyer, Note on a problem of Chowla.Acta Arith. 5 (1959), 417?423.","journal-title":"Acta Arith."},{"key":"CR4","doi-asserted-by":"crossref","first-page":"71","DOI":"10.2307\/2373048","volume":"88","author":"E. Bombieri","year":"1966","unstructured":"E. Bombieri, On exponential sums in finite fields.Amer. J. Math. 88 (1966), 71?105.","journal-title":"Amer. J. Math."},{"key":"CR5","unstructured":"A. L. Chistov and D. Yu. Grigoryev, Polynomial-time factoring of the multivariable polynomials over a global field. LOMI preprint E-5-82, Leningrad, USSR, 1982."},{"key":"CR6","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/0304-3975(91)90157-W","volume":"84","author":"M. Clausen","year":"1991","unstructured":"M. Clausen, A. Dress, J. Grabmeier, andM. Karpinski, On zero testing and interpolation ofk-sparse multivariate polynomials over finite fields.Theor. Computer Science 84 (1991), 151?164.","journal-title":"Theor. Computer Science"},{"key":"CR7","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","volume":"9","author":"D. Coppersmith","year":"1990","unstructured":"D. Coppersmith andS. Winograd, Matrix multiplication via arithmetic progressions.J. Symb. Comp. 9 (1990), 251?280.II. Davenport,Multiplicative Number Theory. Springer-Verlag, Second edition, 1980.","journal-title":"J. Symb. Comp."},{"key":"CR8","doi-asserted-by":"crossref","unstructured":"A. D\u00edaz and E. Kaltofen, On computing greatest common divisors with polynomials given by black boxes for their evaluations. InProc. ISSAC 1995, 1995.","DOI":"10.1145\/220346.220375"},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"M. D. Fried and M. Jarden,Field Arithmetic. Springer-Verlag, 1986.","DOI":"10.1007\/978-3-662-07216-5"},{"key":"CR10","volume-title":"Computers and intractability: A guide to the theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey andD. S. Johnson,Computers and intractability: A guide to the theory of NP-Completeness. W. H. Freeman, San Francisco CA, 1979."},{"issue":"3","key":"CR11","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1137\/0220037","volume":"20","author":"J. Gathen Von zur","year":"1991","unstructured":"J. Von zur Gathen, Tests for permutation polynomials.SIAM J. Comput. 20(3) (1991), 591?602.","journal-title":"SIAM J. Comput."},{"key":"CR12","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1090\/S0025-5718-1985-0790658-X","volume":"45","author":"J. Gathen von zur","year":"1985","unstructured":"J. von zur Gathen andE. Kaltofen, Factorization of multivariate polynomials over finite fields.Math. Comp. 45 (1985), 251?261.","journal-title":"Math. Comp."},{"key":"CR13","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/BF01272074","volume":"2","author":"J. Gathen von zur","year":"1992","unstructured":"J. von zur Gathen andV. Shoup, Computing Frobenius maps and factoring polynomials.Computational complexity 2 (1992), 187?224.","journal-title":"Computational complexity"},{"key":"CR14","doi-asserted-by":"crossref","unstructured":"J. von zur Gathen and I. E. Shparlinski, Components and projections of curves over finite fields. InProc. 5th Int. Symp. on Algorithms and Computation ISSAC '94, vol. 834 ofSpringer Lecture Notes in Computer Science, 1994, 297?305. SIAM J. Comput., to appear.","DOI":"10.1007\/3-540-58325-4_193"},{"key":"CR15","doi-asserted-by":"crossref","unstructured":"J. von zur Gathen and I. E. Shparlinski, Finding points on curves over finite fields. InProc. 36th Ann. IEEE Symp on Foundations of Computer Science, 1995, 284?292.","DOI":"10.1109\/SFCS.1995.492484"},{"key":"CR16","doi-asserted-by":"crossref","unstructured":"D. Yu. Grigoryev and M. Karpinski, An approximation algorithm for the number of zeros of arbitrary polynomials overGF(q). InProc. 20th Ann. IEEE Symp. Foundations of Computer Science, 1991, 662?669.","DOI":"10.1109\/SFCS.1991.185433"},{"key":"CR17","doi-asserted-by":"crossref","first-page":"1059","DOI":"10.1137\/0219073","volume":"19","author":"D. Yu. Grigoryev","year":"1990","unstructured":"D. Yu. Grigoryev, M. Karpinski, andM. F. Singer, Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields.SIAM J. Comp. 19 (1990), 1059?1063.","journal-title":"SIAM J. Comp."},{"key":"CR18","doi-asserted-by":"crossref","unstructured":"R. Hartshorne,Algebraic Geometry. Springer-Verlag, 1977.","DOI":"10.1007\/978-1-4757-3849-0"},{"key":"CR19","unstructured":"M.-D. Huang and D. Ierardi, Counting rational points on curves over finite fields. InProc. 34th Ann. IEEE Symp. on Foundations of Computer Science, Palo Alto CA, 1993, 616?625."},{"key":"CR20","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/S0747-7171(85)80029-8","volume":"1","author":"E. Kaltofen","year":"1985","unstructured":"E. Kaltofen, Fast parallel absolute irreducibility testing.J. Symb. Computation 1 (1985), 57?67.","journal-title":"J. Symb. Computation"},{"issue":"3","key":"CR21","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1016\/0196-6774(89)90038-2","volume":"10","author":"R. M. Karp","year":"1989","unstructured":"R. M. Karp, M. Luby, andN. Madras, Monte-Carlo approximation algorithms for enumeration problems.J. Algorithms 10(3) (1989), 429?448.","journal-title":"J. Algorithms"},{"key":"CR22","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1006\/jagm.1993.1014","volume":"14","author":"M. Karpinski","year":"1993","unstructured":"M. Karpinski andM. Luby, Approximating the number of solutions of aGF[2] polynomial.J. Algorithms 14 (1993), 280?287.","journal-title":"J. Algorithms"},{"key":"CR23","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0022-0000(85)90016-9","volume":"30","author":"A. K. Lenstra","year":"1985","unstructured":"A. K. Lenstra, Factoring multivariate polynomials over finite fields.J. Comput. System Sci. 30 (1985), 235?248.","journal-title":"J. Comput. System Sci."},{"key":"CR24","volume-title":"Finite Fields, vol. 20 ofEncyclopedia of Mathematics and its Applications","author":"R. Lidl","year":"1983","unstructured":"R. Lidl andH. Niederreiter,Finite Fields, vol. 20 ofEncyclopedia of Mathematics and its Applications. Addison-Wesley, Reading MA, 1983."},{"key":"CR25","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1006\/ffta.1995.1003","volume":"1","author":"K. Ma","year":"1995","unstructured":"K. Ma andJ. von zur Gathen, Tests for permutation functions.Finite Fields and their Applications 1 (1995), 31?56.","journal-title":"Finite Fields and their Applications"},{"key":"CR26","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1016\/0022-314X(84)90089-1","volume":"19","author":"K. S. McCurley","year":"1984","unstructured":"K. S. McCurley, Explicit zero-free regions for DirichletL-functions.J. Number Theory 19 (1984), 7?32.","journal-title":"J. Number Theory"},{"key":"CR27","doi-asserted-by":"crossref","first-page":"745","DOI":"10.1090\/S0025-5718-1990-1035941-X","volume":"55","author":"R. Pila","year":"1990","unstructured":"R. Pila, Frobenius maps of Abelian varieties and finding roots of unity in finite fields.Math. Comp. 55 (1990), 745?763.","journal-title":"Math. Comp."},{"key":"CR28","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1016\/S0022-0000(77)80013-5","volume":"14","author":"D. A. Plaisted","year":"1977","unstructured":"D. A. Plaisted, Sparse complex polynomials and polynomial reducibility.J. Comp. and System Sciences 14 (1977), 210?221.","journal-title":"J. Comp. and System Sciences"},{"key":"CR29","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/0304-3975(84)90130-0","volume":"31","author":"D. A. Plaisted","year":"1984","unstructured":"D. A. Plaisted, New NP-hard and NP-complete polynomial and integer divisibility problems.Theor. Computer Science 31 (1984), 125?138.","journal-title":"Theor. Computer Science"},{"key":"CR30","unstructured":"A. Quick, Some GCD and divisibility problems for sparse polynomials. Technical Report 191\/86, Department of Computer Science, University of Toronto, 1986."},{"key":"CR31","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1215\/ijm\/1255631807","volume":"6","author":"J. B. Rosser","year":"1962","unstructured":"J. B. Rosser andL. Schoenfeld, Approximate formulas for some functions of prime numbers.Ill. J. Math. 6 (1962), 64?94.","journal-title":"Ill. J. Math."},{"issue":"170","key":"CR32","first-page":"483","volume":"44","author":"R. J. Schoof","year":"1985","unstructured":"R. J. Schoof, Elliptic curves over finite fields and the computation of square roots modp.Math. Comp. 44(170) (1985), 483?494.","journal-title":"Math. Comp."},{"key":"CR33","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"J. T. Schwartz","year":"1980","unstructured":"J. T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities.J. Assoc. Computing Machinery 27 (1980), 701?717.","journal-title":"J. Assoc. Computing Machinery"},{"key":"CR34","first-page":"397","volume":"296","author":"J.-P. Serre","year":"1983","unstructured":"J.-P. Serre, Sur le nombre des points rationels d'une courbe alg\u00e9brique sur un corps fini.C.R. Acad. Sci. Paris, Ser. 1 296 (1983a), 397?402.","journal-title":"C.R. Acad. Sci. Paris, Ser. 1"},{"key":"CR35","unstructured":"J.-P. Serre, Nombre de points des courbes alg\u00e9briques sur F q .S\u00e9min. de Th\u00e9orie des Nombres de Bordeaux (1983b), 1?8."},{"key":"CR36","doi-asserted-by":"crossref","unstructured":"I. R. Shafarevich,Basic algebraic geometry. Grundlehren Band 213. Springer Verlag, 1974.","DOI":"10.1007\/978-3-642-96200-4"},{"issue":"197","key":"CR37","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1090\/S0025-5718-1992-1106981-9","volume":"58","author":"V. Shoup","year":"1992","unstructured":"V. Shoup, Searching for primitive roots in finite fields.Math. Comp. 58(197) (1992), 369?380.","journal-title":"Math. Comp."},{"issue":"9","key":"CR38","first-page":"1196","volume":"181","author":"I. E. Shparlinski","year":"1990","unstructured":"I. E. Shparlinski, On primitive elements in finite fields and on elliptic curves.Mat. Sbornik 181(9) (1990), 1196?1206. Math. USSR Sbornik71 (1992), 41?50.","journal-title":"Mat. Sbornik"},{"key":"CR39","doi-asserted-by":"crossref","unstructured":"I. E. Shparlinski,Computational and algorithmic problems in finite fields, vol. 88 ofMathematics and its applications. Kluwer Academic Publishers, 1992a.","DOI":"10.1007\/978-94-011-1806-4"},{"key":"CR40","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/BF01202000","volume":"2","author":"I. E. Shparlinski","year":"1992","unstructured":"I. E. Shparlinski, A deterministic test for permutation polynomials.Computational complexity 2 (1992b), 129?132.","journal-title":"Computational complexity"},{"key":"CR41","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1112\/S0025579300012912","volume":"37","author":"I. E. Shparlinski","year":"1990","unstructured":"I. E. Shparlinski andA. N. Skorobogatov, Exponential sums and rational points on complete intersections.Mathematika 37 (1990), 201?208.","journal-title":"Mathematika"},{"key":"CR42","volume-title":"Elements of number theory","author":"I. M. Vinogradov","year":"1954","unstructured":"I. M. Vinogradov,Elements of number theory. Dover Publ. New York NY, 1954."},{"issue":"1","key":"CR43","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1007\/BF01083190","volume":"17","author":"S. G. Vladut","year":"1983","unstructured":"S. G. Vladut andV. G. Drinfeld, Number of points on an algebraic curve.Funktsional'nyi Analis i Prilogenija 17(1) (1983), 68?69. Functional Analysis and its Appl.17 (1983), 53?54.","journal-title":"Funktsional'nyi Analis i Prilogenija"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01202042.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01202042\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01202042","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,24]],"date-time":"2024-12-24T14:23:02Z","timestamp":1735050182000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01202042"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,3]]},"references-count":43,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1996,3]]}},"alternative-id":["BF01202042"],"URL":"https:\/\/doi.org\/10.1007\/bf01202042","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,3]]}}}