A MODULAR INVERSION HARDWARE ALGORITHM WITH A REDUNDANT BINARY REPRESENTATION

被引：0
|
作者：
TAKAGI, N
机构：
来源：
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS | 1993年 / E76D卷 / 08期
关键词：
COMPUTER ARITHMETIC; COMPUTER CRYPTOGRAPH; GREATEST COMMON DIVISOR (GCD); HARDWARE ALGORITHM; MODULAR ARITHMETIC;
D O I：
暂无
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
A hardware algorithm for modular inversion is proposed. It is based on the extended Euclidean algorithm. All intermediate results are represented in a redundant binary representation with a digit set {0, 1, -1}. All addition/subtractions are performed without carry propagation. A modular inversion is carried out in O (n) clock cycles where n is the word length of the modulus. The length of each clock cycle is constant independent of n. A modular inverter based on the algorithm has a regular cellular array structure with a bit slice feature and is very suitable for VLSI implementation. Its amount of hardware is proportional to n.
引用
收藏
页码：863 / 869
页数：7
相关论文
共 50 条
  • [1] SQUARE ROOT HARDWARE ALGORITHM USING REDUNDANT BINARY REPRESENTATION.
    Takagi, Naofumi
    Yajima, Shuzo
    1600, (17):
  • [2] HARDWARE ALGORITHM FOR COMPUTING SINE AND COSINE USING REDUNDANT BINARY REPRESENTATION.
    Systems and Computers in Japan, 1987, 18 (08): : 1 - 9
  • [3] An Improved Modular Inversion Algorithm and Hardware Implementation
    Hu, Jin
    Li, Yongbin
    Hunan Daxue Xuebao/Journal of Hunan University Natural Sciences, 2022, 49 (02): : 101 - 105
  • [4] MODULAR MULTIPLICATION HARDWARE ALGORITHMS WITH A REDUNDANT REPRESENTATION AND THEIR APPLICATION TO RSA CRYPTOSYSTEM
    TAKAGI, N
    YAJIMA, S
    IEEE TRANSACTIONS ON COMPUTERS, 1992, 41 (07) : 887 - 891
  • [5] Hardware design for end-to-end modular exponentiation in redundant number representation
    Sanu, MO
    Swartzlander, EE
    2005 IEEE WORKSHOP ON SIGNAL PROCESSING SYSTEMS - DESIGN AND IMPLEMENTATION (SIPS), 2005, : 65 - 69
  • [6] Efficient Design and Performance Analysis of a Hardware Right-shift Binary Modular Inversion Algorithm in GF(p)
    Choi, Piljoo
    Lee, Mun-Kyu
    Kong, Jeong-Taek
    Kim, Dong Kyue
    JOURNAL OF SEMICONDUCTOR TECHNOLOGY AND SCIENCE, 2017, 17 (03) : 425 - 437
  • [7] HARDWARE ALGORITHMS FOR COMPUTING EXPONENTIALS AND LOGARITHMS USING REDUNDANT BINARY REPRESENTATION.
    Takagi, Naofumi
    Yajima, Shuzo
    Systems and Computers in Japan, 1986, 17 (12): : 11 - 22
  • [8] A binary algorithm with low divergence for modular inversion on SIMD architectures
    Laporta, Maurizio
    Pizzirani, Alberto
    RICERCHE DI MATEMATICA, 2014, 63 : S187 - S199
  • [9] A Redundant Binary Algorithm for RSA
    施荣华
    JournalofComputerScienceandTechnology, 1996, (04) : 416 - 420
  • [10] Research and Hardware Design of Scalable Dual-Field Montgomery Modular Inversion Algorithm
    Chen Lin
    Sun Wan-zhong
    Chen Xing-yuan
    Zhou Chao
    INFORMATION TECHNOLOGY FOR MANUFACTURING SYSTEMS II, PTS 1-3, 2011, 58-60 : 1007 - 1012
12345