Space Efficient <inline-formula> <tex-math notation="LaTeX">$GF(2^m)$ </tex-math></inline-formula> Multiplier for Special Pentanomials Based on <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula>-Term Karatsuba Algorithm
Recently, new multiplication schemes over the binary extension field GF(2<sup>m</sup>) 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 o...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2020-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/8984363/ |
| _version_ | 1818579519070535680 |
|---|---|
| author | Sun-Mi Park Ku-Young Chang Dowon Hong Changho Seo |
| author_facet | Sun-Mi Park Ku-Young Chang Dowon Hong Changho Seo |
| author_sort | Sun-Mi Park |
| collection | DOAJ |
| description | Recently, new multiplication schemes over the binary extension field GF(2<sup>m</sup>) 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/2 m<sup>2</sup> + O(m<sup>3/2</sup>) AND gates and 1/2 m<sup>2</sup> + O(m<sup>3/2</sup>) XOR gates, which nearly correspond to the best results for trinomials. Also, specific comparisons for three fields GF(2<sup>163</sup>), GF(2<sup>283</sup>), and GF(2<sup>571</sup>) 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 bestknown space efficient multipliers, while having the same time complexity. The results show that the proposed multipliers are the best space optimized multipliers. |
| first_indexed | 2024-12-16T07:02:59Z |
| format | Article |
| id | doaj.art-ba391f2954334f7abf850a2492266664 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-16T07:02:59Z |
| publishDate | 2020-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-ba391f2954334f7abf850a24922666642022-12-21T22:40:07ZengIEEEIEEE Access2169-35362020-01-018273422736010.1109/ACCESS.2020.29717028984363Space Efficient <inline-formula> <tex-math notation="LaTeX">$GF(2^m)$ </tex-math></inline-formula> Multiplier for Special Pentanomials Based on <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula>-Term Karatsuba AlgorithmSun-Mi Park0https://orcid.org/0000-0002-3003-6288Ku-Young Chang1https://orcid.org/0000-0001-5529-2774Dowon Hong2https://orcid.org/0000-0001-9690-5055Changho Seo3https://orcid.org/0000-0002-0779-3539Department of Applied Mathematics, Kongju National University, Gongju, South KoreaIntelligent Security Research Group, Electronics and Telecommunications Research Institute (ETRI), Daejeon, South KoreaDepartment of Applied Mathematics, Kongju National University, Gongju, South KoreaDepartment of Applied Mathematics, Kongju National University, Gongju, South KoreaRecently, new multiplication schemes over the binary extension field GF(2<sup>m</sup>) 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/2 m<sup>2</sup> + O(m<sup>3/2</sup>) AND gates and 1/2 m<sup>2</sup> + O(m<sup>3/2</sup>) XOR gates, which nearly correspond to the best results for trinomials. Also, specific comparisons for three fields GF(2<sup>163</sup>), GF(2<sup>283</sup>), and GF(2<sup>571</sup>) 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 bestknown space efficient multipliers, while having the same time complexity. The results show that the proposed multipliers are the best space optimized multipliers.https://ieeexplore.ieee.org/document/8984363/Bit-parallel multiplierKaratsuba algorithmMastrovito approachpentanomialshifted polynomial basis |
| spellingShingle | Sun-Mi Park Ku-Young Chang Dowon Hong Changho Seo Space Efficient <inline-formula> <tex-math notation="LaTeX">$GF(2^m)$ </tex-math></inline-formula> Multiplier for Special Pentanomials Based on <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula>-Term Karatsuba Algorithm IEEE Access Bit-parallel multiplier Karatsuba algorithm Mastrovito approach pentanomial shifted polynomial basis |
| title | Space Efficient <inline-formula> <tex-math notation="LaTeX">$GF(2^m)$ </tex-math></inline-formula> Multiplier for Special Pentanomials Based on <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula>-Term Karatsuba Algorithm |
| title_full | Space Efficient <inline-formula> <tex-math notation="LaTeX">$GF(2^m)$ </tex-math></inline-formula> Multiplier for Special Pentanomials Based on <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula>-Term Karatsuba Algorithm |
| title_fullStr | Space Efficient <inline-formula> <tex-math notation="LaTeX">$GF(2^m)$ </tex-math></inline-formula> Multiplier for Special Pentanomials Based on <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula>-Term Karatsuba Algorithm |
| title_full_unstemmed | Space Efficient <inline-formula> <tex-math notation="LaTeX">$GF(2^m)$ </tex-math></inline-formula> Multiplier for Special Pentanomials Based on <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula>-Term Karatsuba Algorithm |
| title_short | Space Efficient <inline-formula> <tex-math notation="LaTeX">$GF(2^m)$ </tex-math></inline-formula> Multiplier for Special Pentanomials Based on <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula>-Term Karatsuba Algorithm |
| title_sort | space efficient inline formula tex math notation latex gf 2 m tex math inline formula multiplier for special pentanomials based on inline formula tex math notation latex n tex math inline formula term karatsuba algorithm |
| topic | Bit-parallel multiplier Karatsuba algorithm Mastrovito approach pentanomial shifted polynomial basis |
| url | https://ieeexplore.ieee.org/document/8984363/ |
| work_keys_str_mv | AT sunmipark spaceefficientinlineformulatexmathnotationlatexgf2mtexmathinlineformulamultiplierforspecialpentanomialsbasedoninlineformulatexmathnotationlatexntexmathinlineformulatermkaratsubaalgorithm AT kuyoungchang spaceefficientinlineformulatexmathnotationlatexgf2mtexmathinlineformulamultiplierforspecialpentanomialsbasedoninlineformulatexmathnotationlatexntexmathinlineformulatermkaratsubaalgorithm AT dowonhong spaceefficientinlineformulatexmathnotationlatexgf2mtexmathinlineformulamultiplierforspecialpentanomialsbasedoninlineformulatexmathnotationlatexntexmathinlineformulatermkaratsubaalgorithm AT changhoseo spaceefficientinlineformulatexmathnotationlatexgf2mtexmathinlineformulamultiplierforspecialpentanomialsbasedoninlineformulatexmathnotationlatexntexmathinlineformulatermkaratsubaalgorithm |