×

zbMATH — the first resource for mathematics

List decoding of number field codes. (English) Zbl 1321.94137
Summary: This paper presents a list decoding algorithm for the number field codes of V. Guruswami [IEEE Trans. Inf. Theory 49, No. 3, 594–603 (2003; Zbl 1063.94110)]. The algorithm is an implementation of the unified framework for list decoding of algebraic codes of V. Guruswami, A. Sahai and M. Sudan [Proc. 41st Annual Symposium on Foundations of Computer Science, 159–168 (2000); entire collection see Zbl 1131.68300], specialised for number field codes. The computational complexity of the algorithm is evaluated in terms of the size of the inputs and field invariants.

MSC:
94B35 Decoding
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
94B40 Arithmetic codes
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Belabas, K.: A relative van Hoeij algorithm over number fields. J. Symb. Comput. 37(5), 641-668 (2004) · Zbl 1137.11360
[2] Belabas, K.: Topics in computational algebraic number theory. J. Théor. Nr. Bordx. 16(1), 19-63 (2004) · Zbl 1078.11071
[3] Boneh, D.: Finding smooth integers in short intervals using CRT decoding. J. Comput. Syst. Sci. 64(4), 768-784 (2002) · Zbl 1052.68036
[4] Cohen, H.: A Course in Computational Algebraic Number Theory. Graduate Texts in Mathematics, vol. 138. Springer-Verlag, Berlin (1993) · Zbl 0786.11071
[5] Cohen, H.: Advanced Topics in Computational Number Theory. Graduate Texts in Mathematics, vol. 193. Springer-Verlag, New York (2000) · Zbl 0977.11056
[6] Cohn, H., Heninger, N.: Ideal forms of Coppersmith’s theorem and Guruswami-Sudan list decoding. ArXiv:1008.1284v1 (2010). Accessed 24 Jan 2013 · Zbl 1355.65064
[7] Dumas, J.G., Pernet, C., Wan, Z.: Efficient computation of the characteristic polynomial. In: ISSAC’05: Proceedings of the 2005 International Symposium on Symbolic and Algebraic Computation, pp. 140-147. ACM, New York (2005) · Zbl 1360.65123
[8] Edwards, H.M.: Galois Theory. Graduate Texts in Mathematics, vol. 101. Springer-Verlag, New York (1984) · Zbl 0532.12001
[9] Forney Jr., G.D.: Generalized minimum distance decoding. IEEE Trans. Inf. Theory IT-12(2), 125-131 (1966) · Zbl 0253.94007
[10] Gohberg, I., Lancaster, P., Rodman, L.: Matrix Polynomials. Academic Press, New York (1982)
[11] Goldreich, O., Ron, D., Sudan, M.: Chinese remaindering with errors. IEEE Trans. Inf. Theory 46(4), 1330-1338 (2000) · Zbl 1007.94026
[12] Guruswami, V.: Constructions of codes from number fields. IEEE Trans. Inf. Theory 49(3), 594-603 (2003) · Zbl 1063.94110
[13] Guruswami, V.: List Decoding of Error-Correcting Codes. Lecture Notes in Computer Science, vol. 3282. Springer, New York (2004) · Zbl 1075.94001
[14] Guruswami, V., Sahai, A., Sudan, M.: “Soft-decision” decoding of Chinese remainder codes. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, pp. 159-168. IEEE Computer Science Press, Los Alamitos (2000)
[15] Guruswami, V., Sudan, M.: Improved decoding of Reed-Solomon and algebraic-geometry codes. IEEE Trans. Inf. Theory 45(6), 1757-1767 (1999) · Zbl 0958.94036
[16] Guruswami, V., Sudan, M.: Extensions to the Johnson Bound, unpublished manuscript (2001)
[17] Hanrot, G., Pujol, X., Stehlé, D.: Algorithms for the shortest and closest lattice vector problems. In: Coding and Cryptology, Lecture Notes in Computer Science, vol. 6639, pp. 159-190. Springer, Heidelberg (2011) · Zbl 1272.68477
[18] Horowitz, E., Sahni, S.: On computing the exact determinant of matrices with polynomial entries. J. Assoc. Comput. Mach. 22, 38-50 (1975) · Zbl 0293.65026
[19] Howgrave-Graham, N.: Finding small roots of univariate modular equations revisit. In: Darnell, M.J. (ed.) Cryptography and Coding 1997, Lecture Notes in Computer Science, vol. 1355, pp. 131-142. Springer, Heidelberg (1997) · Zbl 0922.11113
[20] Johnson, S.M.: A new upper bound for error-correcting codes. IRE Trans. IT-8(3), 203-207 (1962) · Zbl 0102.34602
[21] Johnson, S.M.: Improved asymptotic bounds for error-correcting codes. IEEE Trans. Inf. Theory IT-9(3), 198-205 (1963) · Zbl 0282.94010
[22] Just, B.: Integer relations among algebraic numbers. In: Kreczmar, A., Mirkowska, G. (eds.) Mathematical Foundations of Computer Science 1989, Lecture Notes in Computer Science, vol. 379, pp. 314-320. Springer, Berlin (1989) · Zbl 0755.68069
[23] Just, B.: Integer relations among algebraic numbers. Math. Comput. 54(189), 467-477 (1990) · Zbl 0689.68061
[24] Kronecker, L.: Grundzüge einer arithmetischen Theorie der algebraischen Grössen. J. Reine. Angew. Math. 92, 1-122 (1882) · JFM 14.0038.02
[25] Landau, S.: Factoring polynomials over algebraic number fields. SIAM J. Comput. 14(1), 184-195 (1985) · Zbl 0565.12002
[26] Lenstra, A.K.: Factoring polynomials over algebraic number fields. In: van Hulzen, J.A. (ed.) Computer Algebra, Lecture Notes in Computer Science, vol. 162, pp. 245-254. Springer, Berlin (1983)
[27] Lenstra, A.K., Lenstra Jr., H.W., Lovász, L.: Factoring polynomials with rational coefficients. Math. Ann. 261(4), 515-534 (1982) · Zbl 0488.12001
[28] Lenstra Jr., H.W.: Codes from algebraic number fields. In: Hazewinkel, M., Lenstra, J.K., Meertens, L.G.L.T. (eds.) Mathematics and Computer Science II, Fundamental Contributions in the Netherlands Since 1945, CWI Monographs, vol. 4, pp. 95-104, North-Holland, Amsterdam (1986)
[29] Lenstra Jr., H.W.: Algorithms in algebraic number theory. Bull. Am. Math. Soc. 26(2), 211-244 (1992) · Zbl 0759.11046
[30] Mandelbaum, D.M.: On a class of arithmetic codes and a decoding algorithm. IEEE Trans. Inf. Theory IT-22(1), 85-88 (1976) · Zbl 0323.94007
[31] Marcus, D.A.: Number Fields. Springer-Verlag, New York (1977) · Zbl 0383.12001
[32] McClellan, M.T.: The exact solution of systems of linear equations with polynomial coefficients. J. Assoc. Comput. Mach. 20, 563-588 (1973) · Zbl 0273.65030
[33] Mignotte, M.: An inequality about factors of polynomials. Math. Comput. 28, 1153-1157 (1974) · Zbl 0299.12101
[34] Narkiewicz, W.: Elementary and Analytic theory of Algebraic Numbers, 3rd edn. Springer-Verlag, Berlin (2004) · Zbl 1159.11039
[35] Nguyen, P.Q., Stehlé, D.: Floating-point LLL revisited. In: Cramer, R. (ed.) EUROCRYPT 2005, Lecture Notes in Computer Science, vol. 3494, pp. 215-233. Springer, Berlin (2005) · Zbl 1137.94353
[36] Nguyen, P.Q., Stehlé, D.: An LLL algorithm with quadratic complexity. SIAM J. Comput. 39(3), 874-903 (2009) · Zbl 1214.11139
[37] Pan, V.: Sequential and parallel complexity of approximate evaluation of polynomial zeros. Comput. Math. Appl. 14(8), 591-622 (1987) · Zbl 0634.65036
[38] Richter, H.: Bemerkung zur Norm der Inversen einer Matrix. Arch. Math. 5, 447-448 (1954) · Zbl 0056.01411
[39] Sidorenko, V., Schmidt, G., Gabidulin, E., Bossert, M., Afanassiev, V.: On polyalphabetic block codes. In: Dinneen, M.J. (ed.) Proceedings of IEEE ISOC Information Theory Workshop 2005 on Coding and, Complexity, pp. 207-210. Rotorua (2005)
[40] Stoer, J., Bulirsch, R.: Introduction to Numerical Analysis, 2nd edn. Texts in Applied Mathematics, vol. 12. Springer-Verlag, New York (1993) · Zbl 0771.65002
[41] Storjohann, A.: Algorithms for Matrix Canonical Forms. Ph.D. thesis, ETH Zürich (2000)
[42] Sudan, M.: Decoding of Reed-Solomon codes beyond the error-correction bound. J. Complex. 13(1), 180-193 (1997) · Zbl 0872.68026
[43] Sudan, M.: Ideal error-correcting codes: unifying algebraic and number-theoretic algorithms. In: Boztas, S., Shparlinski, I.E., (eds.) Proceedings of International 14th Symposium in Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes, Lecture Notes in Computer Science, vol. 2227, pp. 36-45. Springer, Berlin (2001) · Zbl 1057.94516
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.