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

DOI10.3934/amc.2015.9.311zbMath1355.65064arXiv1008.1284OpenAlexW2963934407MaRDI 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

algorithmpolynomial equationsReed-Solomon codesCoppersmith's theoremlist decodinglattice basis reductionGuruswami-Sudan algorithm

Mathematics Subject Classification ID

Related Items (9)

Computing minimal interpolation bases ⋮ List-decoding Barnes-Wall lattices ⋮ Revisiting approximate polynomial common divisor problem and noisy multipolynomial reconstruction ⋮ List Decoding for Binary Goppa Codes ⋮ On the optimality of lattices for the Coppersmith technique ⋮ Row reduction applied to decoding of rank-metric and subspace codes ⋮ List decoding of number field codes ⋮ Power decoding Reed-Solomon codes up to the Johnson radius ⋮ 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

This page was built for publication: Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding