Reduction-Free Multiplication for Finite Fields and Polynomial Rings

被引：0

作者：

Madrigal, Samira Carolina Oliva ^{[1
]}

Saldamli, Gökay ^{[1
]}

Li, Chen ^{[2
]}

Geng, Yue ^{[2
]}

Tian, Jing ^{[2
]}

Wang, Zhongfeng ^{[2
]}

Koc, Cetin Kaya ^{[3
,4
,5
]}

机构：

[1] San Jose State Univ, San Jose, CA USA

[2] Nanjing Univ, Nanjing, Peoples R China

[3] Igdir Univ, Igdir, Turkiye

[4] Nanjing Univ Aeronaut & Astronaut, Nanjing, Peoples R China

[5] Univ Calif Santa Barbara, Santa Barbara, CA USA

来源：

ARITHMETIC OF FINITE FIELDS, WAIFI 2022 | 2023年 / 13638卷

关键词：

Cryptography; Finite field arithmetic; Polynomials rings; Karatsuba-Ofman multiplication; Polynomial bi-partite multiplication; Montgomery multiplication; Interleaved multiplication; Mersenne polynomials; Pseudoprimes; Equally-spaced polynomials; Reduction-free trinomials; Reduction-free multiplication; MODULAR MULTIPLICATION; MASTROVITO MULTIPLIER; PARALLEL;

D O I：

10.1007/978-3-031-22944-2_4

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

The complexity of the multiplication operation over polynomial rings and finite fields drastically changes with the selection of the defining polynomial of the respective mathematical structure. Trinomials and pentanomials are the most natural choices for the best arithmetic. In this paper, we first present a study in which a special type of trinomial does not require any reduction steps. We then introduce two new algorithms, FIKO and RF-FIKO, fully interleaved bit-parallel Karatsuba-Ofman multipliers where the latter is only concerned with the three Karatsuba-Ofman terms and is free from the bipartite reduction circuits. All algorithms are implemented in FPGA and ASIC, and detailed implementation results are presented, showing significant improvements to existing methods.

引用

页码：53 / 78

页数：26

共 38 条

[1] [Anonymous], 1991, THESIS LINKOPING U
[2] Babbage C., 1864, Passages from the Life of a Philosopher
[3] Bajard J.C, 2013, USEFUL ARITHMETIC CR
[4] BLAKLEY GR, 1983, IEEE T COMPUT, V32, P497, DOI 10.1109/TC.1983.1676262
[5] Brakerski Z., 2020, 20201168 IACR EPRINT
[6] Brakerski Z, 2011, LECT NOTES COMPUT SC, V6841, P505, DOI 10.1007/978-3-642-22792-9_29
[7] Brent R., 2011, Notices Amer. Math. Soc, V58, P233
[8] Homomorphic Encryption for Arithmetic of Approximate Numbers
Cheon, Jung Hee
Kim, Andrey
Kim, Miran
Song, Yongsoo
[J]. ADVANCES IN CRYPTOLOGY - ASIACRYPT 2017, PT I, 2017, 10624 : 409 - 437
[9] Low complexity bit-parallel multipliers for GF(2m) with generator polynomial xm+xk+1
Elia, M
Leone, M
Visentin, C
[J]. ELECTRONICS LETTERS, 1999, 35 (07) : 551 - 552
[10] Fast bit parallel-shifted polynomial basis multipliers in GF(2n)
Fan, Haining
Hasan, M. Anwar
[J]. IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS I-REGULAR PAPERS, 2006, 53 (12) : 2606 - 2615

← 1 2 3 4 →