{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,7]],"date-time":"2025-12-07T21:09:25Z","timestamp":1765141765147,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":56,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642254048"},{"type":"electronic","value":"9783642254055"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-25405-5_13","type":"book-chapter","created":{"date-parts":[[2011,11,24]],"date-time":"2011-11-24T06:32:34Z","timestamp":1322116354000},"page":"200-216","source":"Crossref","is-referenced-by-count":8,"title":["Simplified High-Speed High-Distance List Decoding for Alternant Codes"],"prefix":"10.1007","author":[{"given":"Daniel J.","family":"Bernstein","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"13_CR1","unstructured":"\u2014 (no editor): 39th annual symposium on foundations of computer science, FOCS \u201998, November 8-11, 1998, Palo Alto, California, USA. IEEE Computer Society (1998); See [35]"},{"key":"13_CR2","unstructured":"\u2014 (no editor): Proceedings of the 32nd annual ACM symposium on theory of computing. Association for Computing Machinery, New York (2000); See [14]"},{"key":"13_CR3","doi-asserted-by":"publisher","first-page":"2257","DOI":"10.1109\/TIT.2005.850097","volume":"51","author":"M. Alekhnovich","year":"2005","unstructured":"Alekhnovich, M.: Linear diophantine equations over polynomials and soft decoding of Reed-Solomon codes. IEEE Transactions on Information Theory\u00a051, 2257\u20132265 (2005); Cited from \u00a71, \u00a72, \u00a72","journal-title":"IEEE Transactions on Information Theory"},{"key":"#cr-split#-13_CR4.1","doi-asserted-by":"crossref","unstructured":"Augot, D., Barbier, M., Couvreur, A.: List-decoding of binary Goppa codes up to the binary Johnson bound (2010);","DOI":"10.1109\/ITW.2011.6089384"},{"key":"#cr-split#-13_CR4.2","unstructured":"Cited from ??1, ??1, ??3, ??3, ??3, ??3, ??3, ??3, ??6"},{"key":"13_CR5","unstructured":"Barreto, P.S.L.M., Lindner, R., Misoczki, R.: Decoding square-free Goppa codes over F p (2010); Cited from \u00a76"},{"key":"13_CR6","doi-asserted-by":"publisher","first-page":"773","DOI":"10.1016\/j.jsc.2010.03.010","volume":"45","author":"P. Beelen","year":"2010","unstructured":"Beelen, P., Brander, K.: Key equations for list decoding of Reed-Solomon codes and how to solve them. Journal of Symbolic Computation\u00a045, 773\u2013786 (2010); Cited from \u00a71","journal-title":"Journal of Symbolic Computation"},{"key":"13_CR7","volume-title":"Algebraic coding theory","author":"E.R. Berlekamp","year":"1968","unstructured":"Berlekamp, E.R.: Algebraic coding theory. McGraw-Hill, New York (1968); Cited from \u00a71"},{"key":"13_CR8","unstructured":"Bernstein, D.J.: Fast multiplication and its applications. In: [19], pp. 325\u2013384 (2008); Cited from \u00a72, \u00a72, \u00a72, \u00a72"},{"key":"13_CR9","unstructured":"Bernstein, D.J.: Reducing lattice bases to find small-height values of univariate polynomials. In: [19], pp. 421\u2013446 (2008); Cited from \u00a71, \u00a73, \u00a73, \u00a73"},{"key":"13_CR10","doi-asserted-by":"crossref","unstructured":"Bernstein, D.J.: List decoding for binary Goppa codes. In: IWCC 2011 [21], pp. 62\u201380 (2011); Cited from \u00a73, \u00a73","DOI":"10.1007\/978-3-642-20901-7_4"},{"key":"13_CR11","doi-asserted-by":"crossref","unstructured":"Bernstein, D.J., Lange, T., Peters, C.: Attacking and defending the McEliece cryptosystem. In: PQCrypto 2008 [17], pp. 31\u201346 (2008); Cited from \u00a71","DOI":"10.1007\/978-3-540-88403-3_3"},{"key":"13_CR12","doi-asserted-by":"crossref","unstructured":"Bernstein, D.J., Lange, T., Peters, C.: Wild McEliece. In: SAC 2010 [13], pp. 143\u2013158 (2011); Cited from \u00a76","DOI":"10.1007\/978-3-642-19574-7_10"},{"key":"13_CR13","doi-asserted-by":"crossref","unstructured":"Biryukov, A., Gong, G., Stinson, D.R. (eds): Selected areas in cryptography\u201417th international workshop, SAC 2010, Waterloo, Ontario, Canada, August 12-13, 2010, revised selected papers. Lecture Notes in Computer Science, vol. 6544. Springer (2011); See [12]","DOI":"10.1007\/978-3-642-19574-7"},{"key":"13_CR14","doi-asserted-by":"crossref","unstructured":"Boneh, D.: Finding smooth integers in short intervals using CRT decoding. In: STOC 2000 [2], pp. 265\u2013272 (2000); see also newer version [15]; Cited from \u00a73, \u00a73, \u00a73","DOI":"10.1145\/335305.335337"},{"key":"13_CR15","doi-asserted-by":"publisher","first-page":"768","DOI":"10.1006\/jcss.2002.1827","volume":"64","author":"D. Boneh","year":"2002","unstructured":"Boneh, D.: Finding smooth integers in short intervals using CRT decoding. Journal of Computer and System Sciences\u00a064, 768\u2013784 (2002); see also older version [14]","journal-title":"Journal of Computer and System Sciences"},{"key":"13_CR16","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/S0019-9958(60)90287-4","volume":"3","author":"R.C. Bose","year":"1960","unstructured":"Bose, R.C., Ray-Chaudhuri, D.K.: On a class of error correcting binary group codes. Information and Control\u00a03, 68\u201379 (1960); Cited from \u00a71","journal-title":"Information and Control"},{"key":"13_CR17","doi-asserted-by":"crossref","unstructured":"Buchmann, J., Ding, J. (eds.): Post-quantum cryptography, second international workshop, PQCrypto 2008, Cincinnati, OH, USA, October 17-19, 2008, proceedings. Lecture Notes in Computer Science, vol. 5299, Springer (2008); See [11]","DOI":"10.1007\/978-3-540-88403-3"},{"key":"13_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03338-8","volume-title":"Algebraic complexity theory","author":"P. B\u00fcrgisser","year":"1997","unstructured":"B\u00fcrgisser, P., Clausen, M., Shokrollahi, M.A.: Algebraic complexity theory. Springer, Berlin (1997); Cited from \u00a72"},{"key":"13_CR19","series-title":"Mathematical Sciences Research Institute Publications","volume-title":"Surveys in algorithmic number theory","year":"2008","unstructured":"Buhler, J.P., Stevenhagen, P. (eds.): Surveys in algorithmic number theory. Mathematical Sciences Research Institute Publications, vol.\u00a044. Cambridge University Press, New York (2008); See [8], [9]"},{"key":"13_CR20","doi-asserted-by":"crossref","unstructured":"Castagnos, G., Joux, A., Laguillaumie, F., Nguyen, P.Q.: Factoring pq2 with quadratic forms: nice cryptanalyses. In: Asiacrypt 2009 [43], pp. 469\u2013486 (2009); Cited from \u00a73","DOI":"10.1007\/978-3-642-10366-7_28"},{"key":"13_CR21","doi-asserted-by":"crossref","unstructured":"Chee, Y.M., Guo, Z., Ling, S., Shao, F., Tang, Y., Wang, H., Xing, C. (eds.): Coding and cryptology\u2014third international workshop, IWCC 2011, Qingdao, China, May 30-June 3, 2011, proceedings. Lecture Notes in Computer Science, vol.\u00a06639. Springer (2011); See [10]","DOI":"10.1007\/978-3-642-20901-7"},{"key":"13_CR22","doi-asserted-by":"crossref","unstructured":"Chien, R.T., Choy, D.M.: Algebraic generalization of BCH-Goppa-Helgert codes. IEEE Transactions on Information Theory\u00a021, 70\u201379; Cited from \u00a71","DOI":"10.1109\/TIT.1975.1055336"},{"key":"13_CR23","unstructured":"Cohn, H., Heninger, N.: Ideal forms of Coppersmith\u2019s theorem and Guruswami-Sudan list decoding (2010); Cited from \u00a73, \u00a73, \u00a73"},{"key":"13_CR24","doi-asserted-by":"crossref","unstructured":"Coppersmith, D.: Finding a small root of a univariate modular equation. In: Eurocrypt 1996 [44], pp. 155\u2013165 (1996); see also newer version [26]; Cited from \u00a73, \u00a73","DOI":"10.1007\/3-540-68339-9_14"},{"key":"13_CR25","doi-asserted-by":"crossref","unstructured":"Coppersmith, D.: Finding a small root of a bivariate integer equation; factoring with high bits known. In: Eurocrypt 1996 [44], pp. 178\u2013189 (1996); see also newer version [26]; Cited from \u00a73, \u00a73","DOI":"10.1007\/3-540-68339-9_16"},{"key":"13_CR26","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/s001459900030","volume":"10","author":"D. Coppersmith","year":"1997","unstructured":"Coppersmith, D.: Small solutions to polynomial equations, and low exponent RSA vulnerabilities. Journal of Cryptology\u00a010, 233\u2013260 (1997); see also older version [24] and [25]","journal-title":"Journal of Cryptology"},{"key":"13_CR27","doi-asserted-by":"crossref","unstructured":"Darnell, M. (ed.): Cryptography and coding: proceedings of the 6th IMA international conference held at the Royal Agricultural College, Cirencester, December 17-19, 1997. Lecture Notes in Computer Science, vol. 1355. Springer (1997); See [40]","DOI":"10.1007\/BFb0024443"},{"key":"13_CR28","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1109\/TIT.1975.1055435","volume":"21","author":"P. Delsarte","year":"1975","unstructured":"Delsarte, P.: On subfield subcodes of modified Reed-Solomon codes. IEEE Transactions on Information Theory\u00a021, 575\u2013576 (1975); Cited from \u00a71","journal-title":"IEEE Transactions on Information Theory"},{"key":"13_CR29","volume-title":"Modern computer algebra","author":"J. zur Gathen von","year":"2003","unstructured":"von zur Gathen, J., Gerhard, J.: Modern computer algebra, 2nd edn. Cambridge University Press, Cambridge (2003); Cited from \u00a72, \u00a72, \u00a72, \u00a72, \u00a72, \u00a72, \u00a72, \u00a72","edition":"2"},{"key":"13_CR30","doi-asserted-by":"crossref","unstructured":"Giorgi, P., Jeannerod, C.-P., Villard, G.: On the complexity of polynomial matrix computations. In: ISSAC 2003 [49], pp. 135\u2013142 (2003); Cited from \u00a72, \u00a72, \u00a72, \u00a72","DOI":"10.1145\/860854.860889"},{"key":"13_CR31","first-page":"24","volume":"6","author":"V.D. Goppa","year":"1970","unstructured":"Goppa, V.D.: A new class of linear error correcting codes. Problemy Peredachi Informatsii\u00a06, 24\u201330 (1970); Cited from \u00a71, \u00a76","journal-title":"Problemy Peredachi Informatsii"},{"key":"13_CR32","first-page":"41","volume":"7","author":"V.D. Goppa","year":"1971","unstructured":"Goppa, V.D.: Rational representation of codes and (L,g)-codes. Problemy Peredachi Informatsii\u00a07, 41\u201349 (1971) Cited from \u00a71","journal-title":"Problemy Peredachi Informatsii"},{"key":"13_CR33","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1137\/0109020","volume":"9","author":"D. Gorenstein","year":"1961","unstructured":"Gorenstein, D., Zierler, N.: A class of error-correcting codes in p m symbols. Journal of the Society for Industrial and Applied Mathematics\u00a09, 207\u2013214 (1961); Cited from \u00a71","journal-title":"Journal of the Society for Industrial and Applied Mathematics"},{"key":"13_CR34","unstructured":"Guruswami, V.: List decoding of error-correcting codes, Ph.D. thesis, Massachusetts Institute of Technology (2001); Cited from \u00a71"},{"key":"13_CR35","unstructured":"Guruswami, V., Sudan, M.: Improved decoding of Reed-Solomon and algebraic-geometry codes. In: FOCS 1998 [1], pp. 28\u201339 (1998); see also newer version [36]; Cited from \u00a71, \u00a71, \u00a73, \u00a73, \u00a73, \u00a73, \u00a73"},{"key":"13_CR36","doi-asserted-by":"publisher","first-page":"1757","DOI":"10.1109\/18.782097","volume":"45","author":"V. Guruswami","year":"1999","unstructured":"Guruswami, V., Sudan, M.: Improved decoding of Reed-Solomon and algebraic-geometry codes. IEEE Transactions on Information Theory\u00a045, 1757\u20131767 (1999); see also older version [36]; Cited from \u00a73, \u00a73","journal-title":"IEEE Transactions on Information Theory"},{"key":"13_CR37","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1137\/0217019","volume":"17","author":"J. H\u00e5stad","year":"1988","unstructured":"H\u00e5stad, J.: Solving simultaneous modular equations of low degree. SIAM Journal on Computing\u00a017, 336\u2013341 (1988); Cited from \u00a73","journal-title":"SIAM Journal on Computing"},{"key":"13_CR38","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1016\/S0019-9958(74)80005-7","volume":"26","author":"H.J. Helgert","year":"1974","unstructured":"Helgert, H.J.: Alternant codes. Information and Control\u00a026, 369\u2013380 (1974); Cited from \u00a71","journal-title":"Information and Control"},{"key":"13_CR39","first-page":"147","volume":"2","author":"A. Hocquenghem","year":"1959","unstructured":"Hocquenghem, A.: Codes correcteurs d\u2019erreurs. Chiffres\u00a02, 147\u2013156 (1959); Cited from \u00a71","journal-title":"Chiffres"},{"key":"13_CR40","doi-asserted-by":"crossref","unstructured":"Howgrave-Graham, N.: Finding small roots of univariate modular equations revisited. In: Cirencester 1997 [27], pp. 131\u2013142 (1997); Cited from \u00a73, \u00a73","DOI":"10.1007\/BFb0024458"},{"key":"13_CR41","unstructured":"Howgrave-Graham, N.: Computational mathematics inspired by RSA, Ph.D. thesis (1998); Cited from \u00a73, \u00a73"},{"key":"13_CR42","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1109\/TIT.1976.1055516","volume":"22","author":"J. Justesen","year":"1976","unstructured":"Justesen, J.: On the complexity of decoding Reed-Solomon codes. IEEE Transactions on Information Theory\u00a022, 237\u2013238 (1976); Cited from \u00a71","journal-title":"IEEE Transactions on Information Theory"},{"key":"13_CR43","doi-asserted-by":"crossref","unstructured":"Matsui, M. (ed.): Advances in cryptology\u2014ASIACRYPT 2009, 15th international conference on the theory and application of cryptology and information security, Tokyo, Japan, December 6-10, 2009, proceedings. Lecture Notes in Computer Science, vol. 5912. Springer (2009); See [20]","DOI":"10.1007\/978-3-642-10366-7"},{"key":"13_CR44","unstructured":"Maurer, U.M. (ed.): Advances in cryptology\u2014EUROCRYPT 1996: proceedings of the fifteenth international conference on the theory and application of cryptographic techniques Held in Saragossa, May 12-16, 1996. Lecture Notes in Computer Science, vol. 1070. Springer, Berlin (1996); See [24], [25]"},{"key":"13_CR45","doi-asserted-by":"crossref","unstructured":"Mora, T. (ed.): Applied algebra, algebraic algorithms and error-correcting codes: proceedings of the sixth international conference (AAECC-6) held in Rome, July 4-8, 1988. Lecture Notes in Computer Science, vol. 357. Springer, Berlin (1989); See [53]","DOI":"10.1007\/3-540-51083-4"},{"key":"13_CR46","first-page":"459","volume":"6","author":"W. Wesley Peterson","year":"1960","unstructured":"Wesley Peterson, W.: Encoding and error-correction procedures for the Bose-Chaudhuri codes. Transactions of the Institute of Radio Engineers\u00a06, 459\u2013470 (1960); Cited from \u00a71","journal-title":"Transactions of the Institute of Radio Engineers"},{"key":"13_CR47","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1137\/0108018","volume":"8","author":"I.S. Reed","year":"1960","unstructured":"Reed, I.S., Solomon, G.: Polynomial codes over certain finite fields. Journal of the Society for Industrial and Applied Mathematics\u00a08, 300\u2013304 (1960); Cited from \u00a71","journal-title":"Journal of the Society for Industrial and Applied Mathematics"},{"key":"13_CR48","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1109\/TIT.1977.1055732","volume":"23","author":"D.V. Sarwate","year":"1977","unstructured":"Sarwate, D.V.: On the complexity of decoding Goppa codes. IEEE Transactions on Information Theory\u00a023, 515\u2013516 (1977); Cited from \u00a71","journal-title":"IEEE Transactions on Information Theory"},{"key":"13_CR49","unstructured":"Rafael Sendra, J. (ed.): Symbolic and algebraic computation, international symposium ISSAC 2003, Drexel University, Philadelphia, Pennsylvania, USA, August 3-6, 2003, proceedings. Association for Computing Machinery (2003); See [30]"},{"key":"13_CR50","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1006\/jcom.1997.0439","volume":"13","author":"M. Sudan","year":"1997","unstructured":"Sudan, M.: Decoding of Reed Solomon codes beyond the error-correction bound. Journal of Complexity\u00a013, 180\u2013193 (1997); Cited from \u00a71","journal-title":"Journal of Complexity"},{"key":"13_CR51","doi-asserted-by":"publisher","first-page":"518","DOI":"10.1109\/TIT.1976.1055610","volume":"22","author":"Y. Sugiyama","year":"1976","unstructured":"Sugiyama, Y., Kasahara, M., Hirasawa, S., Namekawa, T.: Further results on Goppa codes and their applications to constructing efficient binary codes. IEEE Transactions on Information Theory\u00a022, 518\u2013526 (1976); Cited from \u00a7 6","journal-title":"IEEE Transactions on Information Theory"},{"key":"13_CR52","doi-asserted-by":"publisher","first-page":"4341","DOI":"10.1109\/TIT.2010.2053901","volume":"56","author":"P. Trifonov","year":"2010","unstructured":"Trifonov, P.: Efficient interpolation in the Guruswami-Sudan algorithm. IEEE Transactions on Information Theory\u00a056, 4341\u20134349 (2010); Cited from \u00a71","journal-title":"IEEE Transactions on Information Theory"},{"key":"13_CR53","doi-asserted-by":"crossref","unstructured":"Vall\u00e9e, B., Girault, M., Toffin, P.: How to guess \u2113th roots modulo n by reducing lattice bases. In: AAECC 1989 [45], pp. 427\u2013442 (1989); Cited from \u00a73","DOI":"10.1007\/3-540-51083-4_78"},{"key":"13_CR54","doi-asserted-by":"crossref","unstructured":"Wu, Y.: New list decoding algorithms for Reed-Solomon and BCH codes. IEEE Transactions On Information Theory 54 (2008); Cited from \u00a73, \u00a73","DOI":"10.1109\/TIT.2008.926355"},{"key":"13_CR55","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0022-314X(69)90047-X","volume":"1","author":"H. Zassenhaus","year":"1969","unstructured":"Zassenhaus, H.: On Hensel factorization. I. Journal of Number Theory\u00a01, 291\u2013311 (1969); Cited from \u00a72","journal-title":"Journal of Number Theory"}],"container-title":["Lecture Notes in Computer Science","Post-Quantum Cryptography"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-25405-5_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,19]],"date-time":"2019-06-19T21:08:31Z","timestamp":1560978511000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-25405-5_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642254048","9783642254055"],"references-count":56,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-25405-5_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}