{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T04:39:19Z","timestamp":1648701559502},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1995,3,1]],"date-time":"1995-03-01T00:00:00Z","timestamp":794016000000},"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":[[1995,3]]},"DOI":"10.1007\/bf01277957","type":"journal-article","created":{"date-parts":[[2005,3,24]],"date-time":"2005-03-24T06:00:40Z","timestamp":1111644040000},"page":"76-97","source":"Crossref","is-referenced-by-count":3,"title":["The computational complexity of recognizing permutation functions"],"prefix":"10.1007","volume":"5","author":[{"given":"Keju","family":"Ma","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joachim","family":"von zur Gathen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","unstructured":"Leonard M. Adleman and Ming-Deh Huang,Primality Testing and Abelian Varieties Over Finite Fields, vol. 1512 ofLecture Notes in Mathematics. Springer-Verlag, 1992."},{"key":"CR2","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1974","unstructured":"A. V. Aho, J. E. Hopcroft, andJ. D. Ullman,The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading MA, 1974."},{"key":"CR3","doi-asserted-by":"crossref","unstructured":"E. Bach, Weil bounds for singular curves.AAECC, to appear.","DOI":"10.1007\/BF01195534"},{"key":"CR4","volume-title":"Polynomials and Linear Control Systems, vol. 77 ofMonographs and Textbooks in Pure and Applied Mathematics","author":"S. Barnett","year":"1983","unstructured":"S. Barnett,Polynomials and Linear Control Systems, vol. 77 ofMonographs and Textbooks in Pure and Applied Mathematics. Marcel Dekker, New York NY, 1983."},{"key":"CR5","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":"CR6","doi-asserted-by":"crossref","first-page":"61","DOI":"10.2307\/2373047","volume":"88","author":"E. Bombieri","year":"1966","unstructured":"E. Bombieri andH. Davenport, On two problems of Mordell.Amer. J. Math. 88 (1966), 61?70.","journal-title":"Amer. J. Math."},{"key":"CR7","doi-asserted-by":"crossref","first-page":"693","DOI":"10.1007\/BF01178683","volume":"28","author":"D. G. Cantor","year":"1991","unstructured":"D. G. Cantor andE. Kaltofen, On fast multiplication of polynomials over arbitrary algebras.Acta. Inform. 28 (1991), 693?701.","journal-title":"Acta. Inform."},{"key":"CR8","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":"CR9","doi-asserted-by":"crossref","first-page":"255","DOI":"10.4064\/aa-17-3-255-271","volume":"17","author":"S. D. Cohen","year":"1970","unstructured":"S. D. Cohen, The distribution of polynomials over finite fields.Acta Arith. 17 (1970), 255?271.","journal-title":"Acta Arith."},{"key":"CR10","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1093\/qmath\/14.1.51","volume":"14","author":"H. Davenport","year":"1963","unstructured":"H. Davenport andD. J. Lewis, Notes on congruences (I).Quart. J. Math. Oxford 14 (1963), 51?60.","journal-title":"Quart. J. Math. Oxford"},{"key":"CR11","unstructured":"S. A. Evdokimov, Efficient factorization of polynomials over finite fields and the generalized Riemann hypothesis. Technical Report, Universit\u00e4t Bonn, 1993."},{"key":"CR12","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":"CR13","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 (1991a), 591?602.","journal-title":"SIAM J. Comput."},{"key":"CR14","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1017\/S0004972700028860","volume":"43","author":"J. Gathen von zur","year":"1991","unstructured":"J. von zur Gathen, Values of polynomials over finite fields.Bull. Austral. Math. Soc. 43 (1991b), 141?146.","journal-title":"Bull. Austral. Math. Soc."},{"key":"CR15","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":"CR16","doi-asserted-by":"crossref","unstructured":"J. von zur Gathen, M. Karpinski, and I. E. Shparlinski, Counting curves and their projections. InProc. 25th ACM Symp. Theory of Computing, 1993, 805?812.","DOI":"10.1145\/167088.167292"},{"key":"CR17","volume-title":"Proc. 18th Ann. ACM Symp. Theory of Computing, Berkeley, CA, 1986","author":"S. Goldwasser","year":"1990","unstructured":"S. Goldwasser andJ. Kilian, Almost all primes can be quickly certified. InProc. 18th Ann. ACM Symp. Theory of Computing, Berkeley, CA, 1986, 316?329. See also: J. Kilian,Uses of randomness in algorithms and protocols, ACM Distinguished Doctoral Dissertation Series, MIT Press, Cambridge MA, 1990."},{"key":"CR18","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1215\/S0012-7094-67-03433-3","volume":"34","author":"D. R. Hayes","year":"1967","unstructured":"D. R. Hayes, A geometric approach to permutation polynomials over a finite field.Duke Math. J. 34 (1967), 293?305.","journal-title":"Duke Math. J."},{"key":"CR19","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"},{"key":"CR20","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/S0747-7171(87)80055-X","volume":"4","author":"E. Kaltofen","year":"1987","unstructured":"E. Kaltofen, Deterministic irreducibility testing of polynomials over large finite fields.J. Symb. Comp. 4 (1987), 77?82.","journal-title":"J. Symb. Comp."},{"key":"CR21","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":"CR22","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1080\/00029890.1988.11971991","volume":"95","author":"R. Lidl","year":"1988","unstructured":"R. Lidl andG.L. Mullen, When does a polynomial over a finite field permute the elements of the field?Amer. Math. Monthly 95 (1988), 243?246.","journal-title":"Amer. Math. Monthly"},{"key":"CR23","doi-asserted-by":"crossref","first-page":"71","DOI":"10.2307\/2324822","volume":"100","author":"R. Lidl","year":"1993","unstructured":"R. Lidl andG.L. Mullen, When does a polynomial over a finite field permute the elements of the field?, II.Amer. Math. Monthly 100 (1993), 71?74.","journal-title":"Amer. Math. Monthly"},{"key":"CR24","doi-asserted-by":"crossref","unstructured":"K. Ma and J. von zur Gathen, Counting value sets of functions and testing permutation functions. InAbstract of Int. Conf. Number Theoretic and Algebraic Methods in Computer Science, Moscow, 1993, 62?65. Finite Fields and Their Applications1 (1995), to appear.","DOI":"10.1006\/ffta.1995.1003"},{"key":"CR25","doi-asserted-by":"crossref","first-page":"289","DOI":"10.4064\/aa-12-3-289-299","volume":"12","author":"C. R. MacCluer","year":"1967","unstructured":"C. R. MacCluer, On a conjecture of Davenport and Lewis concerning exceptional polynomials.Acta Arith.12 (1967), 289?299.","journal-title":"Acta Arith"},{"key":"CR26","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1016\/S0022-0000(76)80043-8","volume":"13","author":"G. L. Miller","year":"1976","unstructured":"G. L. Miller, Riemann's hypothesis and tests for primality.J. Comput. System Sci. 13 (1976), 300?317.","journal-title":"J. Comput. System Sci."},{"key":"CR27","unstructured":"G. L. Mullen, Permutation polynomials over finite fields. InProc. 1992 Conf. Finite Fields, Coding Theory, and Advances in Communications and Computing, ed.G. L. Mullen and P. J.-S. Shiue, vol. 141 ofLecture Notes in Pure and Applied Mathematics. Marcel Dekker, 1993, 131?151."},{"key":"CR28","doi-asserted-by":"crossref","unstructured":"V. Pratt, Every prime has a succinct certificate.SIAM J. of Comput. (1975), 214?220.","DOI":"10.1137\/0204018"},{"key":"CR29","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1016\/0022-314X(80)90084-0","volume":"12","author":"M. O. Rabin","year":"1980","unstructured":"M. O. Rabin, Probabilistic algorithms for testing primality.J. of Number Theory 12 (1980), 128?138.","journal-title":"J. of Number Theory"},{"key":"CR30","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/BF02242355","volume":"7","author":"A. Sch\u00f6nhage","year":"1971","unstructured":"A. Sch\u00f6nhage andV. Strassen, Schnelle Multiplikation gro\u00dfer Zahlen.Computing 7 (1971), 281?292.","journal-title":"Computing"},{"key":"CR31","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":"CR32","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.Comput complexity 2 (1992b), 129?132.","journal-title":"Comput complexity"},{"key":"CR33","doi-asserted-by":"crossref","first-page":"787","DOI":"10.1090\/S0025-5718-1993-1176716-3","volume":"60","author":"I. E. Shparlinski","year":"1993","unstructured":"I. E. Shparlinski, On bivariate polynomial factorization over finite fields.Math. Comp. 60 (1993), 787?791.","journal-title":"Math. Comp."},{"key":"CR34","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1137\/0206006","volume":"6","author":"R. Solovay","year":"1977","unstructured":"R. Solovay andV. Strassen, A fast Monte-Carlo test for primality.SIAM J. Comput. 6 (1977), 84?85. Erratum, in7 (1978), 118.","journal-title":"SIAM J. Comput."},{"key":"CR35","unstructured":"D. Wan, Ap-adic lifting lemma and its applications to permutation polynomials. InProc. 1992 Conf. Finite Fields, Coding Theory, and Advances in Communications and Computing, ed.G. L. Mullen and P. J.-S. Shiue, vol. 141 ofLecture Notes in Pure and Applied Mathematics. Marcel Dekker, 1993, 209?216."},{"key":"CR36","doi-asserted-by":"crossref","first-page":"279","DOI":"10.4153\/CMB-1968-033-1","volume":"11","author":"K. S. Williams","year":"1968","unstructured":"K. S. Williams, On exceptional polynomials.Canad. Math. Bull. 11 (1968), 279?282.","journal-title":"Canad. Math. Bull."}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01277957.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01277957\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01277957","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,6]],"date-time":"2020-04-06T12:58:23Z","timestamp":1586177903000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01277957"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,3]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1995,3]]}},"alternative-id":["BF01277957"],"URL":"https:\/\/doi.org\/10.1007\/bf01277957","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,3]]}}}