Interpolation and Approximation of Polynomials in Finite Fields over a\n Short Interval from Noisy Values

2014/01/07 by Óscar García-Morchón, Ronald Rietman, Garcia-Morchon, Oscar +5
Computer Science · Mathematics · #Analytic Number Theory Research #Coding theory and cryptography #Cryptography and Residue Arithmetic #Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT)

paper · pdf · doi:10.48550/arxiv.1401.1331

openalex publication_date 2014/01/07 · openalex created_date 2022/10/06 · openalex updated_date 2026/07/28

Abstract

Motivated by a recently introduced HIMMO key distribution scheme, we consider\na modification of the noisy polynomial interpolation problem of recovering an\nunknown polynomial f(X) \∈ Z[X] from approximate values of the residues of\nf(t) modulo a prime p at polynomially many points t taken from a short\ninterval.\n

Related

• Noisy polynomial interpolation modulo prime powers
• Sparse interpolation over finite fields via low-order roots of unity
• Polynomial Interpolation and Identity Testing from High Powers over\n Finite Fields
• Diversification improves interpolation
• Identity Testing and Interpolation from High Powers of Polynomials of Large Degree over Finite Fields