nach oben

Designs, Codes and Cryptography

Erschienen in:

01.09.2014

List decoding of number field codes

verfasst von: Nicholas Coxon

Erschienen in: Designs, Codes and Cryptography | Ausgabe 3/2014

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This paper presents a list decoding algorithm for the number field codes of Guruswami (IEEE Trans Inf Theory 49:594–603, 2003). The algorithm is an implementation of the unified framework for list decoding of algebraic codes of Guruswami, Sahai and Sudan (Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000), specialised for number field codes. The computational complexity of the algorithm is evaluated in terms of the size of the inputs and field invariants.

Vorheriger Artikel The Ubiquity of the Orders of Fractional Semifields of Even Characteristic

Nächster Artikel A tight bound for frameproof codes viewed in terms of separating hash families

Belabas, K.: A relative van Hoeij algorithm over number fields. J. Symb. Comput. 37(5), 641–668 (2004)

Belabas, K.: Topics in computational algebraic number theory. J. Théor. Nr. Bordx. 16(1), 19–63 (2004)

Boneh, D.: Finding smooth integers in short intervals using CRT decoding. J. Comput. Syst. Sci. 64(4), 768–784 (2002)

Cohen, H.: A Course in Computational Algebraic Number Theory. Graduate Texts in Mathematics, vol. 138. Springer-Verlag, Berlin (1993)

Cohen, H.: Advanced Topics in Computational Number Theory. Graduate Texts in Mathematics, vol. 193. Springer-Verlag, New York (2000)

Cohn, H., Heninger, N.: Ideal forms of Coppersmith’s theorem and Guruswami–Sudan list decoding. ArXiv:1008.1284v1 (2010). Accessed 24 Jan 2013

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)

Edwards, H.M.: Galois Theory. Graduate Texts in Mathematics, vol. 101. Springer-Verlag, New York (1984)

Forney Jr., G.D.: Generalized minimum distance decoding. IEEE Trans. Inf. Theory IT-12(2), 125–131 (1966)

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)

12.

Guruswami, V.: Constructions of codes from number fields. IEEE Trans. Inf. Theory 49(3), 594–603 (2003)

13.

Guruswami, V.: List Decoding of Error-Correcting Codes. Lecture Notes in Computer Science, vol. 3282. Springer, New York (2004)

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)

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)

18.

Horowitz, E., Sahni, S.: On computing the exact determinant of matrices with polynomial entries. J. Assoc. Comput. Mach. 22, 38–50 (1975)

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)

20.

Johnson, S.M.: A new upper bound for error-correcting codes. IRE Trans. IT-8(3), 203–207 (1962)

21.

Johnson, S.M.: Improved asymptotic bounds for error-correcting codes. IEEE Trans. Inf. Theory IT-9(3), 198–205 (1963)

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)

23.

Just, B.: Integer relations among algebraic numbers. Math. Comput. 54(189), 467–477 (1990)

24.

Kronecker, L.: Grundzüge einer arithmetischen Theorie der algebraischen Grössen. J. Reine. Angew. Math. 92, 1–122 (1882)

25.

Landau, S.: Factoring polynomials over algebraic number fields. SIAM J. Comput. 14(1), 184–195 (1985)

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)

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)

30.

Mandelbaum, D.M.: On a class of arithmetic codes and a decoding algorithm. IEEE Trans. Inf. Theory IT-22(1), 85–88 (1976)

31.

Marcus, D.A.: Number Fields. Springer-Verlag, New York (1977)

32.

McClellan, M.T.: The exact solution of systems of linear equations with polynomial coefficients. J. Assoc. Comput. Mach. 20, 563–588 (1973)

33.

Mignotte, M.: An inequality about factors of polynomials. Math. Comput. 28, 1153–1157 (1974)

34.

Narkiewicz, W.: Elementary and Analytic theory of Algebraic Numbers, 3rd edn. Springer-Verlag, Berlin (2004)

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)

36.

Nguyen, P.Q., Stehlé, D.: An LLL algorithm with quadratic complexity. SIAM J. Comput. 39(3), 874–903 (2009)

37.

Pan, V.: Sequential and parallel complexity of approximate evaluation of polynomial zeros. Comput. Math. Appl. 14(8), 591–622 (1987)

38.

Richter, H.: Bemerkung zur Norm der Inversen einer Matrix. Arch. Math. 5, 447–448 (1954)

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)

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)

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)

Titel: List decoding of number field codes
verfasst von: Nicholas Coxon
Publikationsdatum: 01.09.2014
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 3/2014
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-013-9803-x

Springer Professional

List decoding of number field codes

Abstract

Premium Partner

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 3/2014

On the support designs of extremal binary doubly even self-dual codes

Naive configurations

Skeleton simplicial evaluation codes

Kirkman frames having hole type for

On the sharpness of Bruen’s bound for intersection sets in Desarguesian affine spaces

Constructions of almost difference sets from finite fields

Premium Partner