Title :
Efficient Modular Exponentiation with Three-Moduli (2^{n}±1,2^{n}+3)
Author :
Wang, Bangju ; Zhang, Huanguo ; Wang, Yuhua
Author_Institution :
Wuhan Univ., Wuhan
fDate :
July 30 2007-Aug. 1 2007
Abstract :
Modular exponentiation is the basic computation for most public key cryptosystems and digital signal processing. A new signed binary representation (SBR) of operand is presented, which has less weight than NAF when modulus is one of moduli (2nplusmn1,2n+3). The speed of modular squaring with three-moduli (2nplusmn1,2n+3) can be improved using the new SBR by reducing partial products and carries. Based on the result, the speed of computation of modular exponentiation using the new SBR may double that of NAF method for some exponents. According to theoretical analyses and experiment comparing to the other methods mentioned in this paper, the new SBR could improve the speed of modular exponentiation efficiently. Moreover, the SBR of integer can be widely used in secure communication and DSP system.
Keywords :
digital signal processing chips; public key cryptography; redundant number systems; NAF method; digital signal processing; modular exponentiation; modular squaring; public key cryptosystems; redundant number systems; signed binary representation; Algorithm design and analysis; Arithmetic; Artificial intelligence; Computer networks; Concurrent computing; Digital signal processing; Distributed computing; Public key cryptography; Signal processing algorithms; Software engineering;
Conference_Titel :
Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing, 2007. SNPD 2007. Eighth ACIS International Conference on
Conference_Location :
Qingdao
Print_ISBN :
978-0-7695-2909-7
DOI :
10.1109/SNPD.2007.500
