Efficient Arithmetic Modulo Minimal Redundancy Cyclotomic PrimesRobert Granger, Andrew Moss, Nigel Smart, Efficient Arithmetic Modulo Minimal Redundancy Cyclotomic Primes. CSTR-09-004, Claude Shannon Institute, Ireland and University of Bristol. August 2009. PDF, 273 Kbytes.
We introduce a family of prime numbers that we refer to as Minimal Redundancy Cyclotomic Primes (MRCPs). The form of MRCPs is such that when using the field representation and multiplication algorithm we present, multiplication modulo these primes can be up to twice as efficient as multiplication of integer residues. Their adoption will therefore have applications in numerous domains requiring fast prime field arithmetic. This article provides a comprehensive theoretical framework for the use of MRCPs, detailing field and residue representation, conversion and arithmetic algorithms, proofs of correctness, operation counts and parameter generation. As a potential application, we also provide specialised parameters for elliptic curve cryptography, as well as software implementation results.