A Division-Free Toom-Cook Multiplication-Based Montgomery Modular Multiplication

作     者：Gu, Zhen Li, Shuguo 

作者机构：Tsinghua Univ Inst Microelect Beijing 100084 Peoples R China 

出 版 物：《IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS II-EXPRESS BRIEFS》 (IEEE Trans. Circuits Syst. Express Briefs)

年 卷 期：2019年第66卷第8期

页      面：1401-1405页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 

基　　金：National Natural Science Foundation of China 

主　　题：Toom-Cook multiplication Montgomery modular multiplication large integer arithmetic algorithm design and implementation public-key cryptography 

摘      要：Toom-Cook multiplication is a theoretically more efficient multiplication algorithm than traditionally used Karatsuba and schoolbook multiplication but is rarely used in practical hardware designs due to its inherent exact divisions, which are time-consuming and difficult for parallel and serial acceleration. This brief proposes a method of division-free Toom-Cook multiplication based Montgomery modular multiplication, which makes it possible for Toom-Cook multiplication to be applied in practical and efficient hardware implementations. We also provide a hardware implementation of modular multipliers of 256 bits and 1024 bits with advantages on area-time-product over previous researches.