High-Throughput Finite Field Multipliers Using Redundant Basis for FPGA and ASIC Implementations

Overview

Redundant basis (RB) multipliers over Galois Field (GF(2m)) have obtained tremendous popularities in elliptic curve cryptography (ECC) primarily because of their imperceptible hardware cost for squaring and modular devaluation. Multiply operations over a fixed field can be utilized to execute other operations i.e. division, exponentiation and inversion. Multiplication over Galois field can be enforced on a general-purpose machine but it is excessive to use GP machine to resolve cryptographic systems in cost-conscious products.

The need for hardware utilization of fixed range computation functions for the advantages like low cost and high throughput rate for the uttermost real-time applications. The prime of basis to exhibit field parameters namely the polynomial basis, normal basis, triangular basis and redundant basis (RB) has a dominant impact on the achievement of the arithmetic circuits and offer free squaring.

Looking to build projects on VLSI?:

VLSI Kit will be shipped to you and you can learn and build using tutorials. You can start for free today!

1. VLSI Starter

2. VLSI Explorer

3. VLSI Champion

4. VLSI (Career Building Course)

Procedure – For the existing Digit-Serial multipliers, we assume that x to be the basic nth root of unity, elements in a fixed field can be denoted as

L = l0 + l1 x + l2 x2 + ------ + ln-1 xn-1 …………. (1)

Where ai is the element of GF (2) for 0 < i < n-1, such that the given set is defined as the RB for fixed field elements and n is the positive integer not less than m.

Let A and B is the element of GF (2m) can be suggested in RB presentation as

L=i=0n-1lixi …………………………………. (2)

M=i=0n-1mixi ………………………………….. (3)

If N is the Product of L and M, so N = L. M

The procedure steps of basic algorithm are given as below-

1. Initialization: t = [n / w], re, i (-1) = 0 for e = 0, --------, t -1 and i = 0, --------, n -1
2. For complete value sequence of i = 0, 1, 2, ------, n-1, do
3. For complete value sequence of e = 0, 1. 2, ------, t -1, do
4. The value ranges from g = 0 to w -1, do
5. Re, i(g) = Re, i(g-1)
6. End for
7. End for
8. ci=e=0t-1re,i(w-1)
9. End for.

For the derived Digit-Serial RB multiplication algorithm, we can define n bit-shifted forms of operand M at the structure of the bit matrix is given below

M0=i=0n-1mi0xi ………………………………… (4)

Mn-1=i=0n-1min-1xi……………………………. (5)

Where m0i+1=mn-1i

The procedure steps of the derived algorithm are given below-

Inputs: L and M are the couple of elements in GF (2m) to be multiplied.

Output: N = L. M

• Initialization Step: D = 0

• Multiplication Step: 

For u = 0 to Q -1

For v = 0 to P -1

D = D + Bu AuT

End for

End for

• Final Step: C = D

Conclusion 

We have examined the uniqueiterative decomposition finding for RB multiplication to evolve high-throughput digit-serial multipliers by universal formulation. By convenient projection of signal flow graph of derived algorithm and analysing relevant cut-sets for feed-forward cut-set recompute, three innovative high-throughput digit-continual RB multipliers are derived to obtain significantly less area-time-power entanglement than the existing ones.

The outcomes of synthesis reveal that derived structures can manage saving up to 94% of basic algorithm and 60% of a derived algorithm of ADPP for FPGA and ASIC applications respectively, over the best of the current designs.

Did you know

Skyfi Labs helps students learn practical skills by building real-world projects.

You can enrol with friends and receive kits at your doorstep

You can learn from experts, build working projects, showcase skills to the world and grab the best jobs.
Get started today!

• FPGA

• VLSI Design
• FPGA

High-Throughput Finite Field Multipliers Using Redundant Basis for FPGA and ASIC Implementations