Fast and Simple Modular Interpolation Using Factorial Representation

Date

2016

Journal Title

Journal ISSN

Volume Title

Publisher

The American Mathematical Monthly

Abstract

We study a representation for polynomial functions over finite rings. This factorial representation is particularly useful for fast interpolation, and we show that it is computationally preferable to the Lagrange Interpolation Formula (LIF) and to Newton interpolation over finite fields and rings. Moreover, over arbitrary finite rings the calculation of the factorial representation aborts naturally when a given mapping does not arise as a polynomial function.

Description

Keywords

Lagrange Interpolation Formula (LIF)

Citation

G. L. Mullen, D. Panario & D. Thomson (2016) Fast and Simple Modular Interpolation Using Factorial Representation, The American Mathematical Monthly, 123:5, 471-480, DOI: 10.4169/amer.math.monthly.123.5.471