{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T08:53:21Z","timestamp":1776848001301,"version":"3.51.2"},"reference-count":12,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1992,9,1]],"date-time":"1992-09-01T00:00:00Z","timestamp":715305600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Des Codes Crypt"],"published-print":{"date-parts":[[1992,9]]},"DOI":"10.1007\/bf00141967","type":"journal-article","created":{"date-parts":[[2004,11,5]],"date-time":"2004-11-05T20:25:01Z","timestamp":1099686301000},"page":"231-235","source":"Crossref","is-referenced-by-count":11,"title":["Self-witnessing polynomial-time complexity and prime factorization"],"prefix":"10.1007","volume":"2","author":[{"given":"Michael R.","family":"Fellows","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Neal","family":"Koblitz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-68952-9","volume-title":"Foundations of Constructive Mathematics","author":"M.J. Beeson","year":"1985","unstructured":"M.J. Beeson, Foundations of Constructive Mathematics, Springer, Berlin (1985)."},{"key":"CR2","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/S1385-7258(66)50029-4","volume":"Vol. 28","author":"N.G. Bruijn de","year":"1966","unstructured":"N.G. de Bruijn, On the number of positive integers ? x and free of prime factors ? y, Indag. Math. Vol. 28 (1966) pp. 239?247.","journal-title":"Indag. Math."},{"key":"CR3","doi-asserted-by":"crossref","unstructured":"M.R. Fellows and M.A. Langston, On search, decision and the efficiency of polynomial-time algorithms, Proceedings of the ACM Symposium on Theory of Computing (1989) pp. 501?512.","DOI":"10.1145\/73007.73055"},{"key":"CR4","unstructured":"J. Feigenbaum, R.J. Lipton and S.R. Mahaney, A completeness theorem for almost everywhere invulnerable generators, Technical Memorandum, AT&T Bell Laboratories, (February 1989)."},{"key":"CR5","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/0196-6774(87)90043-5","volume":"vol. 8","author":"D.S. Johnson","year":"1987","unstructured":"D.S. Johnson, The NP-completeness column: an ongoing guide, Column 19, J. Algorithms vol. 8 (1987) pp. 285?303.","journal-title":"J. Algorithms"},{"key":"CR6","first-page":"115","volume":"Vol. IX","author":"L.A. Levin","year":"1972","unstructured":"L.A. Levin, Universal enumeration problems, (Russian) Problemy Peredachi Informatsii, Vol. IX (1972) pp. 115?116.","journal-title":"Problemy Peredachi Informatsii"},{"key":"CR7","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1016\/S0022-0000(76)80043-8","volume":"Vol. 13","author":"G.L. Miller","year":"1976","unstructured":"G.L. Miller, Riemann's hypothesis and a test for primality, J. Comput. System Sci. Vol. 13 (1976), pp. 300?317.","journal-title":"J. Comput. System Sci."},{"key":"CR8","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4419-8640-5","volume-title":"A Course in Constructive Algebra","author":"R. Mines","year":"1988","unstructured":"R. Mines, F. Richman and W. Ruitenburg, A Course in Constructive Algebra, Springer-Verlag, New York, (1988)."},{"key":"CR9","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1137\/0204018","volume":"Vol. 4","author":"V.R. Pratt","year":"1975","unstructured":"V.R. Pratt, Every prime has a succinct certificate, SIAM J. Comput. Vol. 4 (1975) pp. 214?220.","journal-title":"SIAM J. Comput."},{"key":"CR10","unstructured":"N. Robertson and P.D. Seymour, Graph minors XIII. Disjoint paths, to appear."},{"key":"CR11","unstructured":"N. Roberston and P.D. Seymour, Graph minors XVI. Wagner's conjecture, to appear."},{"key":"CR12","volume-title":"The Problems of Mathematics","author":"I. Stewart","year":"1987","unstructured":"I. Stewart, The Problems of Mathematics, Oxford University Press, Cambridge (1987)."}],"container-title":["Designs, Codes and Cryptography"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00141967.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF00141967\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00141967","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,3]],"date-time":"2019-04-03T02:00:52Z","timestamp":1554256852000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF00141967"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,9]]},"references-count":12,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1992,9]]}},"alternative-id":["BF00141967"],"URL":"https:\/\/doi.org\/10.1007\/bf00141967","relation":{},"ISSN":["0925-1022","1573-7586"],"issn-type":[{"value":"0925-1022","type":"print"},{"value":"1573-7586","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,9]]}}}