Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding

DOI10.3934/amc.2015.9.311zbMath1355.65064arXiv1008.1284MaRDI QIDQ2516785

Nadia Heninger, Henry Cohn

Publication date: 4 August 2015

Published in: Advances in Mathematics of Communications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1008.1284

zbMATH Keywords

algorithm; polynomial equations; Reed-Solomon codes; Coppersmith's theorem; list decoding; lattice basis reduction; Guruswami-Sudan algorithm

Mathematics Subject Classification ID

94B35: Decoding

65H04: Numerical computation of roots of polynomial equations

Related Items

Row reduction applied to decoding of rank-metric and subspace codes, On the optimality of lattices for the Coppersmith technique, Power decoding Reed-Solomon codes up to the Johnson radius, Revisiting approximate polynomial common divisor problem and noisy multipolynomial reconstruction, List decoding of number field codes, List-decoding Barnes-Wall lattices, Computing minimal interpolation bases, List Decoding for Binary Goppa Codes, Simplified High-Speed High-Distance List Decoding for Alternant Codes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient list decoding of a class of algebraic-geometry codes
• Key equations for list decoding of Reed-Solomon codes and how to solve them
• Fast projection methods for minimal design problems in linear system theory
• Factoring polynomials with rational coefficients
• Small solutions to polynomial equations, and low exponent RSA vulnerabilities
• Efficient algorithms for the Riemann-Roch problem and for addition in the Jacobian of a curve
• List decoding of number field codes
• List-decoding Barnes-Wall lattices
• Oblivious transfer and polynomial evaluation
• Approximate common divisors via lattices
• Faster Algorithms for Multivariate Interpolation With Multiplicities and Simultaneous Polynomial Approximations
• List Decoding for Binary Goppa Codes
• Algebraic Function Fields and Codes
• Linear Diophantine Equations Over Polynomials and Soft Decoding of Reed–Solomon Codes
• On Ideal Lattices and Learning with Errors over Rings
• Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal Redundancy
• Hensel and Newton Methods in Valuation Rings
• Factorization of Multivariate Polynomials Over Finite Fields
• Factoring Multivariate Polynomials over Algebraic Number Fields
• Algorithms in Algebraic Number Theory
• Improved decoding of Reed-Solomon and algebraic-geometry codes
• List decoding of algebraic-geometric codes
• Short Bases of Lattices over Number Fields
• A sieve algorithm for the shortest lattice vector problem
• Using LLL-Reduction for Solving RSA and Factorization Problems
• Multiplying matrices faster than coppersmith-winograd
• Advances in Cryptology - CRYPTO 2003
• Divisors in residue classes, constructively
• Finding smooth integers in short intervals using CRT decoding
• On polynomial congruences