NDLI: A Chinese Remainder Theorem Approach to Bit-Parallel <inline-formula><tex-math>$GF(2^{n})$</tex-math> <alternatives><inline-graphic xlink:type=simple xlink:href=fan-ieq1-2428704.gif/></alternatives></inline-formula> Polynomial Basis Multipliers for Irreducible Trinomials

Content Provider	IEEE Xplore Digital Library
Author	Haining Fan
Copyright Year	1968
Abstract	We show that the step “modulo the degree-n field generating irreducible polynomial” in the classical definition of the GF (2ⁿ) multiplication operation can be avoided. This leads to an alternative representation of the finite field multiplication operation. Combining this representation and the Chinese Remainder Theorem, we design bit-parallel GF (2ⁿ) multipliers for irreducible trinomials uⁿ + u^k + 1 on GF (2) where 1 <; k ≤ n/2. For some values of n, our architectures have the same time complexity as the fastest bit-parallel multipliers-the quadratic multipliers, but their space complexities are reduced. Take the special irreducible trinomial u^2k + u^k + 1 for example, the space complexity of the proposed design is reduced by about 1/8, while the time complexity matches the best result. Our experimental results show that among the 539 values of n such that 4 <; n <; 1,000 and xⁿ + x^k + 1 is irreducible over GF(2) for some k in the range 1 <; k ≤ n=2, the proposed multipliers beat the current fastest parallel multipliers for 290 values of n when (n - 1)/3 ≤ k ≤ n/2: they have the same time complexity, but the space complexities are reduced by 8:4 percent on average.
Sponsorship	IEEE Computer Society Technical Committee on Distributed Process IEEE Computer Society Technical Committee on VLSI IEEE Technical Committee on Computer Architecture IEEE Computer Society
Starting Page	343
Ending Page	352
Page Count	10
File Size	278784
File Format	PDF
ISSN	00189340
Volume Number	65
Issue Number	2
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2016-02-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Polynomials Time complexity Logic gates Computer architecture Delays Mathematical model the Chinese Remainder Theorem Finite field multiplication polynomial basis the chinese remainder theorem
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Computational Theory and Mathematics Software Hardware and Architecture

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

1A Chinese Remainder Theorem Approach to Bit-Parallel GF (2n) Polynomial Basis Multipliers for Irreducible Trinomials (2015)

New Bit Parallel Multiplier With Low Space Complexity for All Irreducible Trinomials Over $GF(2^{n})$

New Bit-Level Serial GF (2^m) Multiplication Using Polynomial Basis

Fast bit-parallel GF(2/sup n/) multiplier for all trinomials

Bit-parallel finite field multipliers for irreducible trinomials

Fast Parallel GF(2^m) Polynomial Multiplication for All Degrees

1Low Space Complexity CRT-based Bit-Parallel GF (2n) Polynomial Basis Multipliers for Irreducible Trinomials

High-Speed Polynomial Basis Multipliers Over $GF(2^{m})$ for Special Pentanomials

Efficient Polynomial Basis Multipliers for Type-II Irreducible Pentanomials

A Chinese Remainder Theorem Approach to Bit-Parallel $GF(2^{n})$ Polynomial Basis Multipliers for Irreducible Trinomials

Similar Documents

1A Chinese Remainder Theorem Approach to Bit-Parallel GF (2n) Polynomial Basis Multipliers for Irreducible Trinomials (2015)

New Bit Parallel Multiplier With Low Space Complexity for All Irreducible Trinomials Over $GF(2^{n})$

New Bit-Level Serial GF (2^m) Multiplication Using Polynomial Basis

Fast bit-parallel GF(2/sup n/) multiplier for all trinomials

Bit-parallel finite field multipliers for irreducible trinomials

Fast Parallel GF(2^m) Polynomial Multiplication for All Degrees

1Low Space Complexity CRT-based Bit-Parallel GF (2n) Polynomial Basis Multipliers for Irreducible Trinomials

High-Speed Polynomial Basis Multipliers Over $GF(2^{m})$ for Special Pentanomials

Efficient Polynomial Basis Multipliers for Type-II Irreducible Pentanomials

A Chinese Remainder Theorem Approach to Bit-Parallel $GF(2^{n})$ Polynomial Basis Multipliers for Irreducible Trinomials