New residue arithmetic based Barrett algorithms: Modular polynomial computations

Hari Krishna Garg; Hanshen Xiao

ICASSP 2017accepted0 citations

New residue arithmetic based Barrett algorithms: Modular polynomial computations

Abstract

We derive a new computational algorithm for Barrett technique for modular polynomial multiplication, termed BA-P. Residue arithmetic is applied to BA-P to obtain a new Barrett algorithm for modular polynomial multiplication (BA-MPM). The work is focused on an algorithm that carries out computation using modular arithmetic without conversion to large degree polynomials. There are several parts to this work. First, we set up a new BA-P using polynomials other than u <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">α</sup> . Second, residue arithmetic based BA-MPM is described. A complete mathematical framework is described including proofs for the results. Third, we present a computational procedure for BA-MPM. Fourth, the BA-MPM is used as a basis for algorithms for modular polynomial exponentiation (MPE). Applications are in areas of signal security and cryptography.

BibTeX

@inproceedings{icassp2017_newresiduearithm,
  title = {New residue arithmetic based Barrett algorithms: Modular polynomial computations},
  author = {Hari Krishna Garg and Hanshen Xiao},
  booktitle = {ICASSP 2017},
  year = {2017}
}