S. Subha · International Journal of Innovative Technology and Exploring Engineering · 2020
Paper Setup must be in A4 size with Margin: Top 0.7”, Bottom 0.7”, Left 0.65”, 0.65”, Gutter 0”, and Gutter Position Top. Pap Abstract: Multiplication is common arithmetic operation in ALU. Many algorithm are proposed for multiplying two unsigned numbers in literature. This paper proposes algorithm to multiply two unsigned binary numbers of any size. The most significant two bits are used to determine the partial product by bit inspection. The rest of partial products are obtained by suitably shifting the previous partial products and adding the terms involving remainders. The remainder is obtained by taking one bit at a time from the MSB-2 position assuming numbers are indexed from zero in LSB to maximum-1 in MSB. The multiplication process is performed as series of additions, shifts in this method. The proposed method is simulated in Quartus2 Toolkit. It is compared to the in-built multiplication process of the tool. A timing improvement of 9.5% with comparable power consumption is obtained with same pin count.
Cited by 2Open access
Xianjin Fang, LI Long-shu · 2007
Algorithms in cryptosystem such as RSA and Diffie-Hellman require the large integer multiplication. This paper introduces classical Knuth multiplication, Karatsuba multiplication and their time complexity, on the basis of which a new Karatsuba trick is presented and proved to be available in theory and in practice. The experiment result reveals that the improved Karatsuba multiplication is more efficient for implementation of large integer multiplication.
Cited by 12
Marc Jóye · Lecture notes in computer science · 2012
Cited by 1
M.C. Mekhallalati, A.S. Ashur, M.K. Ibrahim · Journal of Circuits Systems and Computers · 1996
In this paper, the concept of a new Radix Modular Multiplication Algorithm (MMA) is proposed. The novelty of the new Radix-2 n MMA is that the intermediate partial sums (IPSs) are not restricted to be less than the modulus M, but only to be represented by N bits, where N is the number of bits needed to represent the modulus M. Hence, the IPSs become redundant to the modulus M. Two new Radix-2 n MMAs (for n=2 and 4) based on the proposed concept are considered in detail as well. It is shown that a parallel multiplier based on the new Radix-4 MMA achieves twice the speed of a parallel multiplier based on a recent Radix-2 MMA. This result becomes more significant when it is noted that doubling the speed was achieved without any increase in the hardware requirement. In addition, it is shown that the parallel multiplier based on the new Radix-16 MMA achieves four times the speed of that of the Radix-2 MMA with the same hardware requirement. When compared to the existing Radix-4 MMAs that are based on Carry Save format and Binary Signed Digit (BSD) representation, it is shown that the delay per step of the proposed Radix-4 multiplier is decreased by more than 40% when the intermediate steps are implemented using Carry Save Adders (CSAs).
Cited by 7
M. A. Cherepniov · 2020
Modulo multiplication, where the modulus is an n-digit number, with n approximately equal to 2 9 , is currently the main operation in the discrete logarithm algorithm. If we consider this process as multiplication of big numbers followed by taking modulo (division with remainder), then the latter is the most difficult. We suggest looking at this problem in a different way. Namely, in terms of minimizing time with an unlimited number of computing nodes. This also includes the problem of parallelization on a chip, where the nodes that perform calculations are numerous, but low-power, primarily in memory, and the connections between them are fast. We propose an algorithm for modulo multiplication taking with precalculations stored distributed. The same configuration will significantly reduce the time for multiplication with a fixed multiplier. For the multiplication itself, a parallelized column algorithm is used. The running time of the constructed algorithm on a distributed computing system is estimated by the value O (log n ), and taking into account the conveyor calculation system is performed in one clock cycle.
Cited by 0
Brock J. Prince · 2002
Abstract — Security in today’s networked world is a rising concern. All private information passed through a network or simply transmitted from a source to a destination, must be encrypted to ensure proper security. This is especially important since there are predictions which indicate that the number of wireless network users will surpass the number of wired network users by the year 2004. There are many algorithms that do this, of which most use modular multiplication as a basic building block, but we need to concentrate on hardware that will support them. Montgomery’s algorithm is used to perform fast modular multiplication with minimal complexity. Due to the various sizes of operands and the modulus used in Montgomery’s multiplication and its applications, we are interested in an architecture that implements the algorithm in a flexible manner that can adapt to the required precision. In order to be worthwhile, we must balance execution time, physical area and cost of production. I.
Cited by 0
Guanghua Chen, Ming Liu, Jingming Zhu et al. · 2009
An improved modular multiplication algorithm based on the interleaved multiplication is presented in this paper. Carry save addition (CSA), redundant representation, a fast lookup table and a counter register are used to improve this algorithm. Carry save addition and redundant representation are used to replace other additions like carry select addition, carry lookahead addition and so on, because carry propagation brought by those additions can be prevented by carry save addition, and redundant representation can make the arithmetic operations fast without carry propagation. The fast lookup table with only 7 pre-calculated values can minimize the number of additions, and can only be addressed once in one iteration, which not only speed up, but also save area compared with other literatures used lookup tables. The iteration number can be reduced by a counter register being added in this improved method to compute the number of 0 from the most significant bit of one operand like X. Analysis and emulation result shows the area and time complexity (AT) of the improved method is equal or even less than 2n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> .
Cited by 0
Kálmán Palágyi · 1986
Cited by 0
Stephen Eldridge · International Journal of Computer Mathematics · 1991
This paper describes a method for quickly computing AB mod N where N is odd. It is shown to have significant advantages over other algorithms which make it suitable for use in hardware for public key encryption. Such hardware could run at approximately twice the speed of the best currently available.
Cited by 31
Daniel Král͏̌, Pavel Neogrády, Vladimı́r Kellö · Computer Physics Communications · 1995
Cited by 2
Manohar Mathur, Aarnav · 2023
The speed of oral multiplication using the Vedic formula is amazing. This paper gives a basis for it. Vedic formula fully uses traditional multiplication only but it is well organized to produce quick results. In usual product finding, the result is found only after summing all multiplications. On the contrast, Vedic algorithm does the reverse engineering. It finds what partial multiplications are filling at units, tens, hundreds, etc. The moment a column is filled, summation of all partial products is immediately done and proceeds to the next column. This way oral product finding becomes amazingly speedy. In spite of this, it started losing importance due advent of computers, supercomputers, and also, very cheap calculators. But very soon computer hardware designers were allured to cash the advantageous Vedic algorithm to make the computer speedy at less power consumption and less area.
Cited by 0
2000
Cited by 0
Professor Dr. D. J. Guan · 2003
The Montgomery algorithm for modular multiplication is considered to be the fastest algorithm to compute xy mod n in computers when the values of x, y, and n are large. In this lecture note, we shall describe the Mont-gomery algorithm for modular multiplication. This is one of the notes for the algorithms which my students have difficulty to fully understand. Suppose we want to compute xy mod n in a computer. We first choose a positive integer, r, greater than n and relative prime to n. The value of r is usually 2m for some positive integer m. This is because multiplication, division and modulo by r can be done by shifting or logical operations in computers. Since gcd(r, n) = 1, there are two numbers r−1 and n ′ with 0 &lt; r−1 &lt; n and 0 &lt; n ′ &lt; r, satisfying rr−1 − nn ′ = 1. The algorithm is based on the fact that the computation of xr−1 mod n can be done very efficiently by the algorithm reduce. function reduce (x) begin q: = (x mod r)n ′ mod r; a: = (x+ qn)/r; if a&gt; n then a: = a − n; return a; end Figure 1: Algorithm for the computation of a = xr−1 mod n.
Cited by 0
Ahmed Abdelgawad, Magdy Bayoumi · Lecture notes in electrical engineering · 2012
Cited by 1
XU Zhan-wen · Shenyang Gongye Daxue xuebao · 2006
An efficient algorithm of generate elliptic curves for public key cryptosystems based on discrete logarithm is presented to resist possible attacks such as MOV reduction.The algorithm differs from the(existing) methods of building an elliptic curve with nearly prime order.An elliptic curve constructed by this method contains two large prime factors and satisfies conditions of security.This kind of elliptic curve can be used for various situations where composite order groups are needed.In the cryptosystems based on such elliptic curves,the leakage of information is prevented,and then the cryptosystems are also robust against attacks.Algorithm analysis has been done.Results show that it is much faster to generate a suitable(elliptic) curve with new-scheme than with original scheme.
Cited by 0
Álvaro Bernal, A. Guyot · 1998
This paper examines the characteristics of an alternative architecture for computing a modular multiplication based on Montgomery&apos;s algorithm, useful in performing the RSA Public Key Cryptosystems. An experimental 12x12 bits modular multiplier prototype has been designed with this architecture. Is fabricated by AMS using 0.6 µm-CMOS technology. The architecture, its operation and some simulation results are presented. The evaluation is provided according to the functionality. The active area size is 1.33 x 0.93 mm 2 containing a number of transistors about 4100. 1. Introduction VLSI circuits that accelerate the encryption and decryption of messages using the RSA encryption technique [1] and circuits capable of performing long wordlength modulo multiplication at very high speed attract much interest for cryptography applications. Modular exponentiation operation is the main and more frequently function to process hidden information, for that reason, modular exponentiation plays impor...
Cited by 2
Mohammad S. Obaidat, S.A. Bleha · Computers & Electrical Engineering · 1992
Cited by 2
Hussam Hussein Abuazab, Adel Omar Dahmane, Habib Hamam · 2012
2 Abstract: Several parallel matrix multiplications developed since four decades based on decomposing the multiplied matrices into smaller size blocks, the blocks will be distributed among the processors to run matrix multiplication in shorter time than when only one processor will run the whole matrix multiplications. All parallel matrix multiplications algorithms suffer from three points:
Cited by 1
L. K. Babadzanjanz, Irina Yu. Pototskaya, Yulia Pupysheva et al. · Lecture notes in control and information sciences - proceedings · 2022
Cited by 0
Xin-Ding Zhang, Xiao‐Ming Zhang, Zheng‐Yuan Xue · Scientific Reports · 2016
Hyperentangled states, entangled states with more than one degree of freedom, are considered as promising resource in quantum computation. Here we present a hyperparallel quantum algorithm for matrix multiplication with time complexity O(N(2)), which is better than the best known classical algorithm. In our scheme, an N dimensional vector is mapped to the state of a single source, which is separated to N paths. With the assistance of hyperentangled states, the inner product of two vectors can be calculated with a time complexity independent of dimension N. Our algorithm shows that hyperparallel quantum computation may provide a useful tool in quantum machine learning and "big data" analysis.
Cited by 12Open access