S. Roobini Priya, Prabhat Ranjan · Research Square · 2022
Abstract This paper discusses on Vedic based floating point multiplication. The computations with integers representing very big or tiny numbers is cumbersome due to power aware designs required in IC designs. A good way to express integer values is using the IEEE 754 floating point encoding. DSP applications that use floating point numbers have a wide dynamic range of sophisticated computational processes that call for imprecise calculation techniques. This article describes the implementation and design of the Vedic multiplication and exact floating-point adder-based IEEE 754 channelized floating-point multiplier. The concepts in Vedic mathematics can be meritoriously used to improve logical sequences for implementing computational blocks in system on chip designs. Specific Vedic Sutras are discussed in this paper to implement and create the channelized floating-point multiplier according to IEEE 754. The multiplier's inputs are presented in IEEE 754 32-bit format. For mantissa multiplication, it uses the Urdhva Triyakbhyam sutra. Cases of underflow and overflow are handled through effective designs, to support design of pSoCs with power awareness.
Cited by 1Open access
Ali Mehrabi · Cryptography · 2019
Modular reduction of large values is a core operation in most common public-key cryptosystems that involves intensive computations in finite fields. Within such schemes, efficiency is a critical issue for the effectiveness of practical implementation of modular reduction. Recently, Residue Number Systems have drawn attention in cryptography application as they provide a good means for extreme long integer arithmetic and their carry-free operations make parallel implementation feasible. In this paper, we present an algorithm to calculate the precise value of “ X mod p ” directly in the RNS representation of an integer. The pipe-lined, non-pipe-lined, and parallel hardware architectures are proposed and implemented on XILINX FPGAs.
Cited by 7Open access
Яцків, Н. Г., Левценюк, О. О., Yatskiv, N. G. et al. · ELARTU (Ternopil National Technical University) · 2017
Cited by 0
L. D. Jelfimova · Cybernetics and Systems Analysis · 2019
Cited by 3
Yamato Arai, Yuma Ichikawa, Koji Hukushima · arXiv (Cornell University) · 2023
This study proposes the "adaptive flip graph algorithm", which combines adaptive searches with the flip graph algorithm for finding fast and efficient methods for matrix multiplication. The adaptive flip graph algorithm addresses the inherent limitations of exploration and inefficient search encountered in the original flip graph algorithm, particularly when dealing with large matrix multiplication. For the limitation of exploration, the proposed algorithm adaptively transitions over the flip graph, introducing a flexibility that does not strictly reduce the number of multiplications. Concerning the issue of inefficient search in large instances, the proposed algorithm adaptively constraints the search range instead of relying on a completely random search, facilitating more effective exploration. Numerical experimental results demonstrate the effectiveness of the adaptive flip graph algorithm, showing a reduction in the number of multiplications for a $4\times 5$ matrix multiplied by a $5\times 5$ matrix from $76$ to $73$, and that from $95$ to $94$ for a $5 \times 5$ matrix multiplied by another $5\times 5$ matrix. These results are obtained in characteristic two.
Cited by 0Open access
Igor Kaporin · Numerical Linear Algebra with Applications · 1999
The purpose of this paper is to present an algorithm for matrix multiplication based on a formula discovered by Pan [7]. For matrices of order up to 10 000, the nearly optimum tuning of the algorithm results in a rather clear non-recursive one- or two-level structure with the operation count comparable to that of the Strassen algorithm [9]. The algorithm takes less workspace and has better numerical stability as compared to the Strassen algorithm, especially in Winograd's modification [2]. Moreover, its clearer and more flexible structure is potentially more suitable for efficient implementation on modern supercomputers. Copyright © 1999 John Wiley & Sons, Ltd.
Cited by 41
Walter Groß, Peter Hilton, Jean Pedersen et al. · Mathematics Magazine · 1986
Cited by 0
Marcelo E. Kaihara, Naofumi Takagi · IEEE Transactions on Computers · 2004
A mixed radix-4/2 algorithm for modular multiplication/division suitable for VLSI implementation is proposed. The algorithm is based on Montgomery method for modular multiplication and on the extended Binary GCD algorithm for modular division. Both algorithms are modified and combined into the proposed algorithm so that almost all the hardware components are shared. The new algorithm carries out both calculations using simple operations such as shifts, additions, and subtractions. The radix-2 signed-digit representation is used to avoid carry propagation in all additions and subtractions. A modular multiplier/divider based on the algorithm performs an n-bit modular multiplication/division in O(n) clock cycles where the length of the clock cycle is constant and independent of n. The modular multiplier/divider has a linear array structure with a bit-slice feature and can be implemented with much smaller hardware than that necessary to implement both multiplier and divider separately.
Cited by 55
Hani Mimi, Azman Samsudin, Shahram Jahani · 2013
Window-based elliptic curve multiplication algorithms are more attractive than non-window techniques if precomputation is allowed. Reducing the complexity of elliptic curve point multiplication of the form , which is the dominant operation in elliptic curve cryptography schemes, will reduces the overall complexity of the cryptographic protocol. The wBD is a new window-based elliptic curve multiplication method. It is based on new recoding method called window big-digit (wBD). The wBD is a bidirectional method that can be calculated in both directions based on the amount of the available memory.The available memory is invested in an efficient way since wBD has little number of precomputed points compared to other window methods wich make it more suitable for limited storage devices.The BD recoding method requires only one pass to transform the exponent k from its binary representation to its wBD representation. Moreover, the wBDkeys has the lowest zero-run length among other window methods. Finally, the number of elliptic curve operations in addition to the execution timeof wBD method is measured. Consequently, the wBD is efficient as other window-based methods.
Cited by 0
Hidehiro Kato, Yasuyuki Nogami, Tomoki Yoshida et al. · InTech eBooks · 2010
This paper has first introduced cyclic vector multiplication algorithm (CVMA) that is a multiplication algorithm in extension field. Then, it was also introduced that CVMA was
Cited by 0Open access
Muhammad Rizwan, Enoch Jung, Yoosang Park et al. · 2022
The most scientific and numerical problems can be solved using the system of equations in linear algebra. Matrix-matrix multiplication is the foundation of linear algebra equations, and its optimization has an impact on the overall performance of a system. ScaLAPACK has established itself as the industry standard for dense linear algebraic computations, developed 30 years ago. Owing to advancements in microprocessor architectures, it is difficult to fully utilize the hardware capabilities of legacy software systems on modern architectures and achieve the maximum performance. In this study, we analyzed the effects of matrix size, register blocking parameters, and thread distribution on the performance, and improved our previously implemented matrix-matrix multiplication routine for matrix-panel multiplication, which performed well for large-sized square matrices. We also presented the ScaLAPACK QR factorization performance by replacing the double-precision general matrix-matrix multiplication routine (DGEMM) of ScaLAPACK with our matrix-matrix multiplication routine for a single node Intel Xeon Phi Knights Landing processor.
Cited by 3
Muneeb Abrar, Hassan Elahi, Bilal Ali Ahmad et al. · SN Applied Sciences · 2019
Cited by 6Open access
Sangook Moon · ECTI Transactions on Computer and Information Technology (ECTI-CIT) · 1970
The main back-bone operation in elliptic curve cryptosystems is scalar point multiplication. The most frequently used method implementing the scalar point multiplication, which is performed in the topmost level of GF multiplication and GF division, has been the double-and-add algorithm, which is being recently challenged by NAF (Non-Adjacent Format) algorithm. In this paper, we propose a more efficient and novel approach of a scalar multiplication method than the double-and-add by applying redundant recoding which originates from the radix-4 modified Booth’s algorithm. We call the novel algorithm quad-and-add. After deriving the algorithm, we created a new GF operation, named point quadruple, and verified with calculations of a real-world application to utilize it. Derived numerical expressions were verified using both C programs and HDL (Hardware Description Language). Proposed method of elliptic curve scalar point multiplication can be utilized in many elliptic curve security applications for handling efficient and fast calculations.
Cited by 3Open access
Mostafavi Toroqi, Moeedreza · Espace École de technologie supérieure (École de technologie supérieure) · 2020
Matrix Multiplication is a fundamental mathematical tool and basic problem with various applications in many domains such as data mining and data analyzing. Most of the time, limited-resource clients cannot afford the cost of heavy computations and needs to outsource the information and computations to a powerful and efficient cloud system. In this data exchanging, security and privacy concerning become a significant issue due to the value of some sensitive data such as private personal information or industrial data. The untrusted cloud servers beside malicious adversaries are always a kind of hazard for the clients and increase the risk of information leakage in data outsourcing. There exist many secure algorithms with creative data masking methods which are already usable in the industry, but due to numerous system and treat models, and the importance of the level of the security, new algorithms always emerge to improve the existing schemes. \n \nIn this thesis, we propose four privacy-preserving algorithms based on Strassen’s scheme to provide the desirable result of matrix multiplication for the clients who are not able to process the regular matrix multiplication algorithms because of lake of powerful resources.
Cited by 0Open access
Kruno Golubi� · 2013
Dense matrix-matrix multiplication algorithm is widely used in large scientific applications, and often it is an important factor of the overall performance of the application. Therefore, optimizing this algorithm, both for parallel and serial execution would give an overall performance boost. In this paper we overview the most used dense matrix multiplication optimization techniques applicable for multicore processors. These methods can speedup the multicore parallel execution focusing on reducing the number of memory accesses and improving the algorithm according to hardware architecture and organization.
Cited by 8
Mehdi Nadiri Andabili (22097275), Soheila Nazari (22097278), Tohid Moosazadeh (22097281) · Figshare · 2025
Pseudocode for the CORDIC algorithm to compute multiplication.
Cited by 0Open access
Hui Li, Ruixia Zhang, Junkai Yi et al. · 2013
Scalar multiplication is a very time consuming process, thus plays an important role in elliptic curves digital signature algorithm (ECDSA). To speed up the scalar multiplication process, in this paper, we propose a novel scheme, different from both principles mentioned above, to accelerate the execution of scalar multiplication by elaborately generating a random scalar in ECDSA. Experimental results illustrate that the proposed method can greatly reduce the number of point addition operations in scalar multiplication compared with other existing methods.
Cited by 8
Hao Wang · 2025
Matrix multiplication is one of the most basic and important operation in many computation applications, which comes with high time complexity. Several parallel algorithms have been proposed to speed up the operation. Among them, DNS algorithm is more promising, for its theoretical linear speedup and high theoretical speedup efficiency near 1.0. This article conducts an experimental study on the algorithm with TianHe-II supercomputer of National Supercomputer Center in Guangzhou. The results, with maximum speedup of 74.005 and maximum speedup efficiency of 1.561 beyond our experimental setup, indicate that DNS algorithm can obtain high speedup and superlinear speedup efficiency. In the future, several in-thread parallel frameworks will be adopted to accelerate local matrix block multiplication for advanced performance.
Cited by 0
David W. C. Beasley · 2004
Cited by 1
A. Pincin · IEEE Transactions on Computers · 1989
A new algorithm is presented for computing the product of two elements in a finite field by means of sums and products in a fixed subfield. The algorithm is based on a normal basis representation of fields and assumes that the dimension m of the finite field over the subfield is a highly composite number. A very fast parallel implementation and a considerable reduction in the number of computations are allowed, in comparison to some methods discussed in the literature.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
Cited by 24