DocumentCode :
1467022
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
Volume :
6
Issue :
1
fYear :
2012
fDate :
3/1/2012 12:00:00 AM
Firstpage :
14
Lastpage :
19
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;
fLanguage :
English
Journal_Title :
Information Security, IET
Publisher :
iet
ISSN :
1751-8709
Type :
jour
DOI :
10.1049/iet-ifs.2010.0114
Filename :
6166939
Link To Document :
بازگشت