Title :
Obtaining more Karatsuba-like formulae over the binary field
Author :
Fan, Haining ; Gu, Ming ; Sun, Jian ; Lam, Kam-Yiu
Author_Institution :
Key Lab. for Inf. Syst. Security, Tsinghua Univ., Beijing, China
fDate :
3/1/2012 12:00:00 AM
Abstract :
The aim of this study is to find more Karatsuba-like formulae for a fixed set of moduli polynomials in GF(2)[x]. To this end, a theoretical framework is established. The authors first generalise the division algorithm, and then present a generalised definition of the remainder of integer division. Finally, a generalised Chinese remainder theorem is used to achieve their initial goal. As a by-product of the generalised remainder of integer division, the authors rediscover Montgomery´s N-residue and present a systematic interpretation of definitions of Montgomery´s multiplication and addition operations.
Keywords :
cryptography; number theory; polynomials; Karatsuba-like formulae; Montgomery N-residue; Montgomery multiplication; addition operations; binary field; division algorithm; generalised Chinese remainder theorem; integer division remainder; moduli polynomials;
Journal_Title :
Information Security, IET
DOI :
10.1049/iet-ifs.2010.0114