Efficient Arithmetic Modulo Cyclotomic PrimesRobert Granger, Andrew Moss, Nigel Smart, Efficient Arithmetic Modulo Cyclotomic Primes. CSTR-08-001, University of Bristol. February 2008. PDF, 109 Kbytes.
We propose efficient algorithms for performing arithmetic modulo a class of integers we refer to as cyclotomic primes. Our algorithms are based on recent work by Chung and Hasan, who described an efficient modular reduction algorithm for so-called low-weight polynomial form integers (LWPFIs). Our central idea is to embed arithmetic modulo these primes into a slightly larger ring, which has a particularly simple cyclic structure. We argue that these embedding rings optimise the performance of the Chung-Hasan reduction method, as well as multiplication cost. We also present the first interleaved modular multiplication algorithm for LWPFIs, and for cyclotomic primes in particular. To validate this algorithm we present empirical evidence of a $20$\% performance improvement obtained from a fair comparison between a family of cyclotomic primes, and a standard interleaved Montgomery multiplier, for various bitlengths.