{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T03:46:20Z","timestamp":1776829580356,"version":"3.51.2"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1993,4,1]],"date-time":"1993-04-01T00:00:00Z","timestamp":733622400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1993,4]]},"DOI":"10.1007\/bf01228507","type":"journal-article","created":{"date-parts":[[2005,2,25]],"date-time":"2005-02-25T19:18:45Z","timestamp":1109359125000},"page":"313-328","source":"Crossref","is-referenced-by-count":15,"title":["Sieve algorithms for perfect power testing"],"prefix":"10.1007","volume":"9","author":[{"given":"Eric","family":"Bach","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jonathan","family":"Sorenson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1137\/0217012","volume":"2","author":"E. Bach","year":"1988","unstructured":"E. Bach. How to generate factored random numbers.SIAM J. Comput.,2:179?193, 1988.","journal-title":"SIAM J. Comput."},{"key":"CR2","doi-asserted-by":"crossref","first-page":"1143","DOI":"10.1137\/0215083","volume":"4","author":"E. Bach","year":"1986","unstructured":"E. Bach, G. Miller and J. Shallit. Sums of Divisors, perfect numbers, and factoring.SIAM J. Comput.,4:1143?1154, 1986.","journal-title":"SIAM J. Comput."},{"issue":"185","key":"CR3","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1090\/S0025-5718-1989-0947467-1","volume":"52","author":"E. Bach","year":"1989","unstructured":"E. Bach and J. Shallit. Factoring with cyclotomic polynomials.Math. Comp.,52(185):201?219, 1989.","journal-title":"Math. Comp."},{"key":"CR4","doi-asserted-by":"crossref","first-page":"994","DOI":"10.1137\/0215070","volume":"15","author":"P. W. Beame","year":"1986","unstructured":"P. W. Beame, S. A. Cook and H. J. Hoover. Log depth circuits for division and related problems.SIAM J. Comput.,15:994?1003, 1986.","journal-title":"SIAM J. Comput."},{"key":"CR5","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/B978-0-12-697560-4.50014-9","volume-title":"Analytical Computational Complexity","author":"R. P. Brent","year":"1976","unstructured":"R. P. Brent. Multiple precision zero-finding methods and the complexity of elementary function evaluation. In J. F. Traub, editor,Analytical Computational Complexity, pp. 151?176. Academic Press, New York, 1976."},{"key":"CR6","doi-asserted-by":"crossref","unstructured":"A. Cobham. The recognition problem for the set of perfect squares. InProceedings of the 7th Annual Symposium on Switching and Automata Theory, pp. 78?87, 1966.","DOI":"10.1109\/SWAT.1966.30"},{"key":"CR7","first-page":"197","volume":"23","author":"G. E. Collins","year":"1969","unstructured":"G. E. Collins. Computing multiplicative inverses inGF(p).Math. Comp.,23:197?200, 1969.","journal-title":"Math. Comp."},{"key":"CR8","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-5927-3","volume-title":"Multiplicative Number Theory","author":"H. Davenport","year":"1980","unstructured":"H. Davenport.Multiplicative Number Theory. Springer-Verlag, New York, 1980."},{"issue":"153","key":"CR9","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1090\/S0025-5718-1981-0595059-1","volume":"36","author":"J. Dixon","year":"1981","unstructured":"J. Dixon. Asymptotically fast factorization of integers.Math. Comp.,36(153):255?260, 1981.","journal-title":"Math. Comp."},{"key":"CR10","doi-asserted-by":"crossref","unstructured":"S. Goldwasser and J. Kilian. Almost all primes can be quickly certified. InProceedings of the 18th Annual ACM Symposium on Theory of Computing, pp. 316?329, 1986.","DOI":"10.1145\/12130.12162"},{"key":"CR11","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1016\/0022-314X(73)90047-4","volume":"5","author":"S. W. Golomb","year":"1973","unstructured":"S. W. Golomb. A new arithmetic function of combinatorial significance.J. Number Theory,5:218?223, 1973.","journal-title":"J. Number Theory"},{"issue":"4","key":"CR12","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1016\/0196-6774(89)90004-7","volume":"10","author":"J. L. Hafner","year":"1989","unstructured":"J. L. Hafner and K. S. McCurley. On the distribution of running times of certain integer factoring algorithms.J. Algorithms,10(4):531?556, 1989.","journal-title":"J. Algorithms"},{"key":"CR13","volume-title":"An Introduction to the Theory of Numbers","author":"G. H. Hardy","year":"1979","unstructured":"G. H. Hardy and E. M. Wright.An Introduction to the Theory of Numbers, Oxford University Press, Oxford, 5th edition. 1979.","edition":"5th edition"},{"key":"CR14","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-1779-2","volume-title":"A Classical Introduction to Modern Number Theory","author":"K. Ireland","year":"1982","unstructured":"K. Ireland and M. Rosen.A Classical Introduction to Modern Number Theory. Springer-Verlag, New York, 1982."},{"key":"CR15","doi-asserted-by":"crossref","first-page":"217","DOI":"10.4064\/aa-11-2-217-240","volume":"11","author":"W. B. Jurkat","year":"1965","unstructured":"W. B. Jurkat and H.-E. Richert. An improvement of Selberg's sieve method I.Acta. Arith.,11:217?240, 1965.","journal-title":"Acta. Arith."},{"key":"CR16","series-title":"Handbook of Theoretical Computer Science Series, Volume A","first-page":"871","volume-title":"Algorithms and Complexity","author":"R. Karp","year":"1990","unstructured":"R. Karp and V. Ramachandran. Parallel algorithms for shared memory machines. In J. van Leeuwen, editor,Algorithms and Complexity, Chapter 17, pp. 871?941. Handbook of Theoretical Computer Science Series, Volume A. Elsevier, Amsterdam, and MIT Press, Cambridge, MA, 1990."},{"key":"CR17","volume-title":"The Art of Computer Programming: Seminumerical Algorithms, Volume 2","author":"D. E. Knuth","year":"1981","unstructured":"D. E. Knuth.The Art of Computer Programming: Seminumerical Algorithms, Volume 2, 2nd edition. Addison-Wesley, Reading, MA. 1981.","edition":"2nd edition"},{"key":"CR18","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1016\/0304-3975(76)90050-5","volume":"3","author":"D. E. Knuth","year":"1976","unstructured":"D. E. Knuth and L. Trabb Pardo. Analysis of a simple factorization algorithm.Theoret. Comput. Sci.,3:321?348, 1976.","journal-title":"Theoret. Comput. Sci."},{"key":"CR19","doi-asserted-by":"crossref","unstructured":"A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse and J. M. Pollard. The number field sieve. InProceedings of the 22nd Annual ACM Symposium on Theory of Computing, pp. 564?572, 1990.","DOI":"10.1145\/100216.100295"},{"key":"CR20","doi-asserted-by":"crossref","first-page":"649","DOI":"10.2307\/1971363","volume":"126","author":"H. W. Lenstra Jr","year":"1987","unstructured":"H. W. Lenstra, Jr. Factoring integers with elliptic curves.Ann. of Math.,126:649?673, 1987.","journal-title":"Ann. of Math."},{"key":"CR21","unstructured":"V. Miller. Private communication, 1989."},{"key":"CR22","doi-asserted-by":"crossref","unstructured":"C. A. Neff. Specified precision polynomial root isolation is in NC. InProceedings of 31st Annual IEEE Symposium on Foundations of Computer Science, pp. 152?162, 1990.","DOI":"10.1109\/FSCS.1990.89534"},{"key":"CR23","doi-asserted-by":"crossref","unstructured":"V. Pan. Fast and efficient algorithms for sequential and parallel evaluation of polynomial zeros and of matrix polynomials. InProceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science, pp. 522?531, 1985.","DOI":"10.1109\/SFCS.1985.25"},{"key":"CR24","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1017\/S0305004100049252","volume":"76","author":"J. M. Pollard","year":"1974","unstructured":"J. M. Pollard. Theorems on factorization and primality testing.Math. Proc. Cambridge Philos. Soc.,76:521?528, 1974.","journal-title":"Math. Proc. Cambridge Philos. Soc."},{"key":"CR25","series-title":"Perspectives in Computing Series, Volume 15","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/B978-0-12-386870-1.50014-9","volume-title":"Discrete Algorithms and Complexity: Proceedings of the Japan-US Joint Seminar","author":"C. Pomerance","year":"1987","unstructured":"C. Pomerance. Fast, rigorous factorization and discrete logarithm algorithms. In D. S. Johnson, A. Nishizeke, A. Nozaki, and H. S. Wilf, editors,Discrete Algorithms and Complexity: Proceedings of the Japan-US Joint Seminar, pp. 119?143. Perspectives in Computing Series, Volume 15, Academic Press, Boston. 1987."},{"key":"CR26","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1016\/0196-6774(83)90014-7","volume":"4","author":"P. Pritchard","year":"1983","unstructured":"P. Pritchard. Fast compact prime number sieves (among others).J. Algorithms,4:332?344, 1983.","journal-title":"J. Algorithms"},{"key":"CR27","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1215\/ijm\/1255631807","volume":"6","author":"J. B. Rosser","year":"1962","unstructured":"J. B. Rosser and L. Schoenfeld. Approximate formulas for some functions of prime numbers.Illinois J. Math.,6:64?94, 1962.","journal-title":"Illinois J. Math."},{"key":"CR28","unstructured":"J. Shallit. Course Notes for Number Theory and Algorithms. Dartmouth College, 1989."},{"key":"CR29","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/0020-0190(90)90195-4","volume":"33","author":"V. Shoup","year":"1990","unstructured":"V. Shoup. On the deterministic complexity of factoring polynomials over finite fields.Inform. Process. Lett.,33:261?267, 1990.","journal-title":"Inform. Process. Lett."},{"key":"CR30","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1007\/BF03021203","volume":"54","author":"E. C. Titchmarsh","year":"1930","unstructured":"E. C. Titchmarsh. A divisor problem.Rend. Circ. Mat. Palermo,54:414?429, 1930.","journal-title":"Rend. Circ. Mat. Palermo"},{"key":"CR31","doi-asserted-by":"crossref","first-page":"1073","DOI":"10.1090\/S0025-5718-1979-0528061-7","volume":"33","author":"S. S. Wagstaff Jr.","year":"1979","unstructured":"S. S. Wagstaff, Jr., Greatest of the least primes in arithmetic progressions having a certain modulus.Math. Comp.,33:1073?1080, 1979.","journal-title":"Math. Comp."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01228507.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01228507\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01228507","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,5]],"date-time":"2020-04-05T23:35:53Z","timestamp":1586129753000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01228507"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,4]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1993,4]]}},"alternative-id":["BF01228507"],"URL":"https:\/\/doi.org\/10.1007\/bf01228507","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,4]]}}}