检索结果-内蒙古大学图书馆

Area-Efficient Barrett Modular Multiplication With Optimized karatsuba algorithm

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 2024年第12期43卷 4626-4639页

作者： Zhang, Bo Yan, Shoumeng Ant Grp Co Ltd Comp Syst Lab Ant Res Hangzhou 310000 Peoples R China

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 & LeftFloor;AB/2(f)& RightFloor;, and modular multiplication (MM) AB mod 2(f). Taking the 4-term karatsuba algorithm as an example, an N-bit multiplication AB can be decomposed into 9 (N/4) -bit multiplications. Our optimized approaches for truncated multiplication and MM require an area equivalent to only 6.5 (N/4) -bit multiplications when f approximate to N . 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.

关键词： Barrett modular multiplication (BMM) cryptosystem karatsuba algorithm modular multiplication (MM) Barrett modular multiplication (BMM) cryptosystem karatsuba algorithm modular multiplication (MM)

来源：评论

学校读者我要写书评

暂无评论

Hardware Addition Over Finite Fields Based On Booth-karatsuba algorithm

引用

COMPUTER JOURNAL 2024年第8期67卷 2643-2666页

作者： Perez, J. Ayuso University Carlos III of Madrid CT Engineering Group Madrid Spain

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.

关键词： modular addition Booth algorithm karatsuba algorithm hardware binary adder finite field operations Galois field arithmetic

来源：评论

学校读者我要写书评

暂无评论

Space Efficient GF (2^m) Multiplier for Special Pentanomials Based on n-Term karatsuba algorithm

引用

IEEE ACCESS 2020年 8卷 27342-27360页

作者： Park, Sun-Mi Chang, Ku-Young Hong, Dowon Seo, Changho Kongju Natl Univ Dept Appl Math Gongju 32588 South Korea ETRI Intelligent Secur Res Grp Daejeon 34129 South Korea

Recently, new multiplication schemes over the binary extension field GF (2(m)) based on an n-term karatsuba algorithm have been proposed for irreducible trinomials. In this paper, we extend these schemes for trinomials to any irreducible polynomials. We introduce some new types of pentanomials and propose multipliers for those pentanomials utilizing the extended schemes. We evaluate the rigorous space and time complexities of the proposed multipliers, and compare those with similar bit-parallel multipliers for pentanomials. As a main contribution, the best space complexities of our multipliers are 1/2m(2) + O(m(3/2)) AND gates and 1/2 m(2) + O(m(3/2)) XOR gates, which nearly correspond to the best results for trinomials. Also, specific comparisons for three fields GF (2(163)), GF (2(283)), and GF (2(571)) recommended by NIST show that the proposed multiplier has roughly 40% reduced space complexity compared to the fastest multipliers, while it costs a few more XOR gate delay. It is noticed that our space complexity gain is much greater than the time complexity loss. Moreover, the proposed multiplier has about 21% reduced space complexity than the best-known space efficient multipliers, while having the same time complexity. The results show that the proposed multipliers are the best space optimized multipliers.

关键词： Bit-parallel multiplier karatsuba algorithm Mastrovito approach pentanomial shifted polynomial basis

来源：评论

学校读者我要写书评

暂无评论

Some Improvements of the Parallel karatsuba algorithm Student paper 19

Some Improvements of the Parallel Karatsuba Algorithm Studen...

引用

INFOTEH-JAHORINA 19th International Symposium (INFOTEH)

作者： Delibasic, Mirza Habibovic, Amra Hanjalic, Naida Husagic, Envera Univ Sarajevo Fac Elect Engn Sarajevo Bosnia & Herceg

ISBN: (数字)9781728147758

ISBN: (纸本)9781728147758

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.

关键词： Long integer multiplication karatsuba algorithm OpenMP

来源：评论

学校读者我要写书评

暂无评论

Low Space Complexity GF(2^m) Multiplier for Trinomials Using n-Term karatsuba algorithm

引用

IEEE ACCESS 2019年 7卷 27047-27064页

作者： Park, Sun-Mi Chang, Ku-Young Hong, Dowon Seo, Changho Kongju Natl Univ Dept Appl Math Gongju 32588 South Korea ETRI Intelligent Secur Res Grp Daejeon 34129 South Korea

We propose bit-parallel GF(2(m)) multipliers for irreducible trinomials using an n-term karatsuba algorithm and Mastrovito approach, which are generalizations of the newly proposed multiplication scheme for a specific trinomial. The complexities of the proposed multipliers for GF(2(m)) depend on the choice of an irreducible trinomial x(m) + x(k) + 1 defining GF (2(m)) and values n, m(0) such that m = nm(0) or m = nm(0) + 1. It is possible to achieve a space-time tradeoff by choosing proper values for k, n, and m(0). For the purpose of a specific comparison, we compare the proposed multipliers with the best-known multipliers for an odd m is an element of [399;450] for which there exists an irreducible trinomial of degree m. As a result, the proposed multipliers achieve the lowest space complexities among similar bit-parallel multipliers (they have roughly 40% reduced space complexities compared with the fastest multiplier). On the other hand, their time complexities match or are at most 2T(X) higher than the fastest multipliers, where T-X is the delay of one 2-input XOR gate.

关键词： Bit-parallel multiplier trinomial karatsuba algorithm Mastrovito approach shifted polynomial basis

来源：评论

学校读者我要写书评

暂无评论

Efficient Bit-Parallel Multiplier for All Trinomials Based on n-Term karatsuba algorithm

引用

IEEE ACCESS 2020年 8卷 173491-173507页

作者： Park, Sun-Mi Chang, Ku-Young Hong, Dowon Seo, Changho Kongju Natl Univ Dept Appl Math Gongju 32588 South Korea Elect & Telecommun Res Inst ETRI Cyber Secur Res Div Daejeon 34129 South Korea

Recently, hybrid multiplication schemes over the binary extension field GF (2(m)) based on n-term karatsuba algorithm (KA) have been proposed for irreducible trinomials. Their complexities depend on a decomposition of m and the choice of a generation polynomial. However, these multipliers have some limitations on a decomposition of m or generation polynomial x(m) + x(k) + 1 such that m >= 2k. In this paper, we loosen such limited conditions. We present a new hybrid bit-parallel multiplier based on n-term KA for any irreducible trinomial x(m) + x(k) + 1 (0 < k < m), where m is decomposed as m D nm(0) + r with 0 < r < m(0) and 1 < n. (Here, various values for n, m(0) and r may be chosen.) To this end, we generalize the previously proposed multiplication scheme for x(nm0+1) +x(k) + 1 into x(nm0C+r) + x(k) + 1. We evaluate the explicit complexity of the proposed multiplier. Specific comparisons show that the proposed multiplier achieves the lowest space complexity with the same or lower time complexity among hybrid multipliers. Compared to the fastest multipliers, the time complexity of the proposed multiplier costs only T-X higher while its space complexity is much lower (it has roughly 40% reduced space complexity), where T-X is the delay of one 2-input XOR gate.

关键词： Hybrid bit-parallel multiplier trinomial karatsuba algorithm Mastrovito approach shifted polynomial basis

来源：评论

学校读者我要写书评

暂无评论

Design of a digit-serial multiplier over GF(2^m) using a karatsuba algorithm

引用

JOURNAL OF THE CHINESE INSTITUTE OF ENGINEERS 2019年第7期42卷 602-612页

作者： Lee, Trong-Yen Liu, Min-Jea Huang, Chia-Han Fan, Chia-Chen Tsai, Chia-Chun Wu, Haixia Natl Taipei Univ Technol Dept Elect Engn Taipei Taiwan Natl Chiao Tung Univ Dept Comp Sci Hsinchu Taiwan Nanhua Univ Dept Comp Sci & Informat Engn Chiayi Taiwan Beijing Inst Technol Sch Informat & Elect Beijing Peoples R China

A karatsuba algorithm (KA) is used for highly accurate multiplication using a divide and conquer approach. A new approach to a polynomial digit-serial multiplier that uses an optimal digit size (d) for KA decomposition has recently been proposed. In this study, the proposed architecture uses three small multipliers to derive an optimal digit size (d) for the case of trinomial based fields. Using the proposed KA decomposition, this study establishes five types of sub-quadratic multipliers, which are, the recombined m-bit exponentiation multipliers using a KA. The theoretical results show that the proposed polynomial exponentiation multipliers that use a KA have a value of (d x m)/2 and involve significantly less time and area complexity than existing digit-serial multipliers. The simulation results for the proposed method demonstrate a respective 68.20%, 77.37%, 72%, 83.18%, 36.66% decrease in area x time over GF(2(36)), GF(2(84)), GF(2(126)), GF(2(204)) and GF(2(340)).

关键词： Digit-serial multiplier finite-field karatsuba algorithm

来源：评论

学校读者我要写书评

暂无评论

Hardware Efficient Fast FIR Filter Based on karatsuba algorithm 5

Hardware Efficient Fast FIR Filter Based on Karatsuba Algori...

引用

5th International Conference on Modern Circuits and Systems Technologies (MOCAST)

作者： Kyritsis, Evangelos Pekmestzi, Kiamal Natl Tech Univ Athens Dept Elect & Comp Engn Athens 15780 Greece

ISBN: (纸本)9781467396806

In this work, an efficient implementation of a programmable Finite Impulse Response (FIR) filter based on the use of the karatsuba Multiplication algorithm (KMA) is presented. In this FIR filter circuit, a parallel, Modified Booth (MB) pre-encoded, Carry-Save (CS) Wallace tree multiplier is used as a building block. The KMA is a fast divide and conquer algorithm for the multiplication of large numbers. As a result, the proposed circuit is highly efficient in terms of speed, area and power in comparison with the Conventional FIR filter architecture. Simulations of FIR filters in transposed form made over standard-cell implementation based on a Faraday 90nm technology show an average reduction of about 15% in the delay, 9% in area and 17% in power.

关键词： Finite impulse response (FIR) filter karatsuba algorithm VLSI Design

来源：评论

学校读者我要写书评

暂无评论

Subquadratic Space-Complexity Digit-Serial Multipliers Over GF(2^m) Using Generalized (a,b)-Way karatsuba algorithm

引用

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS I-REGULAR PAPERS 2015年第4期62卷 1091-1098页

作者： Lee, Chiou-Yng Meher, Pramod Kumar Lunghwa Univ Sci & Technol Comp Informat & Network Engn Taoyuan 33306 Taiwan Nanyang Technol Univ Sch Comp Engn Singapore 639798 Singapore

karatsuba algorithm (KA) is popularly used for high-precision multiplication by divide-and-conquer approach. Recently, subquadratic digit-serial multiplier based on (a, 2)-way KA decomposition is proposed in [1]. In this paper, we extend a (a, 2)-way KA to derive a generalized (a, 2)-way KA decomposition with a not equal b. We have shown that (a, 2)-way KA and mult-way KA are special cases of the proposed (a, 2)-way KA decomposition. Based on the proposed KA decomposition, we have established two types of subquadratic digit-serial multipliers, namely, the KA-based multiplier and the recombined KA-based multiplier. From theoretical analysis, as well as, from synthesis results we have shown that the proposed KA-based multipliers have significantly less delay and less area-delay product (ADP) compared to the existing naive digit-serial multipliers.

关键词： Digit-serial multiplication elliptic curve cryptography karatsuba algorithm subquadratic space complexity multiplication

来源：评论

学校读者我要写书评

暂无评论

Design of a karatsuba Multiplier to Accelerate Digital Signature Schemes on Embedded Systems 10

Design of a Karatsuba Multiplier to Accelerate Digital Signa...

引用

10th Nordic Circuits and Systems Conference

作者： Navarro-Torrero, Pablo Camacho-Ruiz, Eros Martinez-Rodriguez, Macarena C. Brox, Piedad US CSIC CNM Inst Microelect Sevilla IMSE Seville Spain

ISBN: (纸本)9798331517663;9798331517670

This paper presents the design and implementation of a karatsuba multiplier to accelerate digital signature schemes on embedded systems. The karatsuba algorithm is integrated into hardware accelerators for RSA and EdDSA, representing a fundamental component of contemporary, state-of-the-art implementations. A hardware/software co-design methodology is employed, implementing the architectures on a System-on-Chip platform that combines programmable logic with an ARM processor. The results showcase enhanced resource consumption and timing performance for both signature generation and verification, confirming the superiority of EdDSA over RSA when utilizing the same karatsuba multiplier core and coding techniques.

关键词： karatsuba algorithm digital signatures elliptic curves FPGA HW/SW co-design RSA EdDSA

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：