Skip to content
Free planNo credit card requiredStart writing
AI for Research home
AI for Research home
Dashboard
Sign inGet started

Search 250 million research papers

Read the abstract, see who wrote it and who cites it, and get the citation in APA, MLA, Chicago or Harvard.

About 260 papers for “Karatsuba algorithm”

On Karatsuba Multiplication Algorithm

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

Efficient Digit-Serial Multiplier Employing Karatsuba Algorithm

Shyan‐Ming Yuan, Chiou‐Yng Lee, Chia-Chen Fan · 2016

This paper presents a efficient digit-serial GF(\( 2^{m} \)) multiplier. The proposed architecture using digit-serial of concept to combine the principle of Karatsuba multiplier which can reduce circuit space complexity, also it is suitable for Elliptic Curve Cryptography (ECC) technology. We knows that the password system’s operation core is a multiplier, however that password system’s multiplier is very big, so it is necessary for reduce the area and time’s complexity. This paper is implement three smaller multiplier and digit-serial in FPGA to reduce time and area complexity. This method uses \( \frac{3dm}{2} \) AND gate, 6 m + n+ \( \frac{3dm}{2} + \frac{m}{2} \) +d-7 XORs and 3 m-3 registers. The paper using Altera FPGA Quartus II to simulate four different multipliers, 36 × 36, 84 × 84, 126 × 126 and 204 × 204, and implemented on Cyclone II EP2C70F896C8 experimental platform. The experimental results show that the proposed multipliers have lower time complexity than the existing digit-serial structures. The proposed architecture can reduce the time × space complexity decreasing when the bit-size of multiplier is increasing.

Cited by 0

Generalizations of the Karatsuba Algorithm for Polynomial Multiplication

André Weimerskirch, Christof Paar · 2007

In this work we generalize the classical Karatsuba Algorithm (KA) for polynomial multiplication to (i) polynomials of arbitrary degree and (ii) recursive use. We determine exact complexity expressions for the KA and focus on how to use it with the least number of operations. We develop a rule for the optimum order of steps if the KA is used recursively. We show how the usage of dummy coefficients may improve performance. Finally we provide detailed information on how to use the KA with least cost, and also provide tables that describe the best possible usage of the KA for polynomials up to a degree of 127.

Cited by 0

A Less Recursive Variant of Karatsuba-Ofman Algorithm

For Multiplying Operands, Serdar S. Erdem, Gebze Yüksek et al. · 2003

We propose a new algorithm for fast multiplication of large integers having a precision of 2 computer words, where k is an integer. The algorithm is derived from the Karatsuba-Ofman Algorithm and has the same asymptotic complexity. However, the running time of the new algorithm is slightly better, and it makes one third as many recursive calls.

Cited by 0

VLSI Implementation of Karatsuba Algorithm and Its Evaluation

Syunji Yazaki, Kôki Abe · 2013

VLSI implementation of Karatsuba algorithm for multi-digit multiplication was investigated. We designed 32-bit recursive Karatsuba multiplier (RKM) and found that its critical path delay and area cost are 9.44ns and 0.228mm 2, respectively. Next we designed and evaluated RKM of larger bits. For bit length less than 2 9, Wallace tree multiplier (WTM) has less area cost than RKM, while RKM has less area cost than WTM for bit length larger than 2 9. The area cost of multiplier of 2 9 bits is approximately 30mm 2. Critical path delay of RKM is always larger than that of WTM. We should use WTM instead of RKM as combinational circuits for iterative Karatsuba multiplier (IKM) to have better cost performance. keywords:multi-digit multiplier, Karatsuba, VLSI 1

Cited by 0

Instruction sequence expressions for the Karatsuba multiplication algorithm

J.A. Bergstra, C.A. Middelburg · UvA-DARE (University of Amsterdam) · 2013

The Karatsuba multiplication algorithm is an algorithm for computing the product of two natural numbers represented in the binary number system. This means that the algorithm actually computes a function on bit strings. The restriction of this function to bit strings of any given length can be computed according to the Karatsuba multiplication algorithm by a finite instruction sequence that contains only instructions to set and get the content of Boolean registers, forward jump instructions, and a termination instruction. We describe the instruction sequences concerned for the restrictions to bit strings of the different lengths by uniform terms from an algebraic theory.

Cited by 4Open access

Enhanced high speed modular multiplier using karatsuba algorithm

C. Prema, C. S. Mainkanda Babu · 2013

High speed modular multiplier is a primary requirement of multi-core processors because of critical applications such as security and high performance, many of which requires efficient and reliable hardware implementations. The classical methods are developed using Barrett's reduction and Montgomery multiplications. But the intermediate quotient is very large and main trade-off of this project is speed. To overcome this karatsuba multiplication is used to enhance the speed and potential of parallel processing. The result shows about the comparison of area and power of the existing algorithms. From the result our proposed method achieves high speed compared with other modular multipliers. The different type of algorithms developed as architectures and the digit serial basic concept is established to each algorithms. Also it is used to increase the potential achieve the parallel implementation. The proposed modular multiplier is done on the proposed architecture of digit serial multipliers using existing mathematical algorithms. This method reaches the maximum speed and hence the area gets reduced. Implementation of the proposed modular algorithm in this project have the less power consumption compared to their counterparts with similar modular algorithms.

Cited by 8

Design of High Speed FFT using UrdhvaTiryagbhyam Algorithm and Karatsuba Algorithm

S. S. Kerur, Mustaq Kunnur · International Journal of Engineering and Advanced Technology · 2020

In gift scenario each method has to be compelled to be quick, adept and simple. Fast Fourier transform (FFT) may be a competent algorithmic program to calculate the N purpose Discrete Fourier transform (DFT).It has huge applications in communication systems, signal processing and image processing and instrumentation. However the accomplishment of FFT needs immense range of complicated multiplications, therefore to create this method quick and simple. It’s necessary for a number to be quick and power adept. To influence this problem the mixture of Urdhva Tiryagbhyam associate degreed Karatsuba algorithmic program offers is an adept technique of multiplication [1]. Vedic arithmetic is that the aboriginal system of arithmetic that includes a distinctive technique of calculation supported sixteen Sutras. Using these techniques within the calculation algorithms of the coprocessor can reduce the complexness, execution time, area, power etc. The distinctiveness during this project is Fast Fourier Transform (FFT) style methodology exploitation mixture of Urdhva Tiryagbhyam and Karatsuba algorithmic program based mostly floating point number. By combining these two approaches projected style methodology is time-area-power adept [1] [2]. The code writing is completed in verilog and also the FPGA synthesis on virtex 5 is completed using Xilinx ISE 14.5.

Cited by 0Open access

Area-Efficient Barrett Modular Multiplication With Optimized Karatsuba Algorithm

Bo Zhang, Shoumeng Yan · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · 2024

This article presents an area-efficient Barrett modular multiplication (BMM) algorithm, facilitating the development of cryptosystems like fully homomorphic encryption. Instead of implementing three normal multiplications required by classic BMM, our proposed BMM introduces optimizations for multiplication AB, truncated multiplication <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\lfloor AB/2^{f} \rfloor $ </tex-math></inline-formula>, and modular multiplication (MM) <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$AB ~\text {mod}~2^{f}$ </tex-math></inline-formula>. Taking the 4-term Karatsuba algorithm as an example, an N-bit multiplication AB can be decomposed into <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$9~(N/4)$ </tex-math></inline-formula>-bit multiplications. Our optimized approaches for truncated multiplication and MM require an area equivalent to only <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$6.5~(N/4)$ </tex-math></inline-formula>-bit multiplications when <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$f\approx N$ </tex-math></inline-formula>. Furthermore, our optimized Karatsuba multiplications introduce efficient (E, I) matrix pairs, circumventing area overhead from complex I matrices and sign extension in multiplication. We also employ encode algorithm to eliminate many additions needed in BMM and inside multiplications, significantly shortening critical path. Experimental results demonstrate the advantages of our proposed BMM in terms of throughput and area efficiency.

Cited by 5

Integrated NTT-Karatsuba for fast multiplication of NTRU Algorithm

Muhammad Fathan Rivaldi, Rohmat Gunawan, Irani Hoeronis · Journal of Information Technology and Computer Science · 2026

The increasing threat of attacks from quantum computers requires the development of more efficient and secure post-quantum cryptographic algorithms, one of which is NTRU. The main challenge in this algorithm lies in the high complexity of large-dimensional polynomial multiplication operations and parameter sizes that affect system performance. This research implements the Hybridized Number Theoretic Transform and Karatsuba calculation methods with compressed parameters in the C programming language and integrates them into the NTRU algorithm. The evaluation was conducted by measuring the key generation, encryption, and decryption processing times, as well as analyzing the size of the public key, ciphertext, and bandwidth requirements before and after parameter compression. The experimental results show that this method is able to significantly reduce the modulus q value without compromising security, while increasing execution time efficiency. These findings prove that the hybrid NTT–Karatsuba method with compressed parameters supports the practical implementation of the NTRU algorithm in resource-constrained environments.

Cited by 0Open access

Implementing digital filter using karatsuba algorithm with Chebyshev coefficient

Vikram S. Deshmukh, Mahesh S. Pawar · 2015

In this paper, we present a new method that help to improve the performance of a digital Finite Impulse Response filter (FIR) using the methodology of implementing polynomial multiplication in Chebyshev form. Our approach has a two step. First study of Karatsuba algorithm is applied to polynomials constructed by using Chebyshev coefficients. Then by using this multiplier implementing transposed form of FIR filter. Digital filter is of multiplier, adder and delay element. Here, we are using Parallel prefix adder which provides a high speed addition and the Karatsuba multiplier with Chebyshev form making the characteristics of a digital filter close to ideal one.

Cited by 0

Karatsuba Algorithm based Modified Architecture for Carry Save Multiplication

Amrita Soni, Athul Biju, Sneha Shrivastav et al. · 2025

In many high-performance computing systems, such as DSPs, AI accelerators, and cryptographic processors, multiplication is an essential operation. However, issues with power consumption, latency, and area efficiency are frequently present in traditional multipliers like Carry Save and Karatsuba-based systems. This paper suggests an improved multiplier architecture that incorporates three key innovations: a recursive Karatsuba algorithm to lower computational complexity; a NAND-based carry chain for faster and more compact addition; and an Improved Full Adder (IFA) that uses NAND-based logic to reduce transistor count and switching activity. Compared to traditional Carry Save multipliers, there is a 30.3 percent reduction in latency, a 39.1 percent area saving, and a 23.3 percent power consumption reduction. These improvements make the proposed design highly suitable for low-power embedded systems and high-speed MAC units, with scalability potential for higher-bit multipliers in future implementations.

Cited by 0

Exploration of Karatsuba Algorithm for Efficient Barrett Modular Multiplication

Bo Zhang, Mingzhe Zhang, Shoumeng Yan · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · 2025

As a key operation in contemporary cryptosystems, modular multiplication occupies non-negligible latency and area. We first show optimizations of the k-term Karatsuba algorithm for AB/rk and ABmodrk that play a significant role in modular multiplication. We prove the bijective mapping between AB/rk and ABmodrk, and propose four methods to build efficient Karatsuba multiplications with arbitrary k values. For k1,32, the multiplication cost for AB/rk and ABmodrk is 25.04% less than that for AB on average. Furthermore, we investigate the correlation between operand bitwidth N of modular multiplication and decomposition factor k of the Karatsuba algorithm. Karatsuba multiplication with a larger k needs less area in the multiplication phase, but also has a more complex implementation in the evaluation and interpolation phases. Experimental results for Barrett modular multiplication with N=32, 64, 128, 256 and k=1, 2, 4, 8 show that modular multiplication achieves the minimal area when N/k=32. For instance, our proposed design when N=256 saves 21.57% area and 25.71% area/throughput, compared with state-of-art designs.

Cited by 0

Hybrid series-parallel polynomial multiplier based on Karatsuba algorithm

Yang Liu, Jing Tian, Suwen Song et al. · 2024

Polynomial multiplication leads to a significant computational and spatial burden in cryptographic algorithms, posing challenges to optimization endeavors. In this work, we propose a hybrid series-parallel polynomial multiplier based on Karatsuba algorithm. The proposed multiplier can achieve a substantial decrease in the area, while slightly increase the cycle time, thus decrease Area-Delay Product (ADP) greatly, which significantly outperforms the conventional polynomial multiplication algorithms. We implement this architecture on FPGA and achieves the improvement of 32% in area and 49% in ADP compared with conventional algorithm.

Cited by 1

Some Improvements of the Parallel Karatsuba Algorithm: Student paper

Mirza Delibasic, Amra Habibovic, Naida Hanjalic et al. · 2020

Multiplying long integers is one of the basic mathematical operations used mostly in cryptography. The topic of this paper is experimental testing of different implementations of the Karatsuba algorithm for multiplying long integers using shared memory parallel programming. Different ways of using OpenMP were considered for optimizing implementations of the algorithm and the experiment results were analysed and compared. The parallel implementation has achieved a significant speedup compared to the sequential code, with the maximum achieved speedup of 9 on a 12 core CPU.

Cited by 0

Hardware Addition Over Finite Fields Based On Booth–Karatsuba Algorithm

J. A. Romera Perez · The Computer Journal · 2024

Abstract Two algorithms, both based around multiplication, one defined by Andrew Donald Booth in 1950 and the other defined by Anatoly Alexeevitch Karatsuba in 1960 can be applied to other types of operations. We know from recent results that to perform some algebraic transformations it is more efficient to calculate an inverse effect of a smaller magnitude together with an original action with a higher rank, than the initial operation, reaching the final element with less transitions. In this paper, we present an addition algorithm on $\mathbb {Z}/m\mathbb {Z}$ of big-integer numbers based on these concepts, using an alternative to traditional hardware implementation for binary addition based on FULL-ADDER cells, allowing the reduction of space complexity compared with other techniques, such as carry-lookahead, letting us calculate a modular addition in an optimal order complexity of $\mathcal {O}(n)$ without adding more complexity due to reduction operations.

Cited by 0Open access

Resource Efficient Single Precision Floating Point Multiplier Using Karatsuba Algorithm

K V Gowreesrinivas, P. Samundiswary · Indonesian Journal of Electrical Engineering and Informatics (IJEEI) · 2018

In floating point arithmetic operations, multiplication is the most required operation for many signal processing and scientific applications. 24-bit length mantissa multiplication is involved to obtain the floating point multiplication final result for two given single precision floating point numbers. This mantissa multiplication plays the major role in the performance evaluation in respect of occupied area and propagation delay. This paper presents the design and analysis of single precision floating point multiplication using karatsuba algorithm with vedic multiplier with the considering of modified 2x1 multiplexers and modified 4:2 compressors in order to overcome the drawbacks in the existing techniques . Further , the performance analysis of single precision floating point multiplier is analyzed in terms of area and delay using Karatsuba Algorithm with different existing techniques such as 4x1 multiplexers and 3:2 compressors and modified techniques such as 2x1 multiplexers, 4:2 compressors. From the simulation results, it is observed that single precision floating point multiplication with karatsuba algorithm using modified 4:2 compressor with XOR-MUX logic provides better performance with efficient usage of resources such as area and delay than that of existing techniques. All the blocks involved for floating point multiplication are coded with Verilog and synthesized using Xilinx ISE Simulator.

Cited by 2Open access