Method for multiplication in Galois fields using programmable circuits
First Claim
Patent Images
1. A method for multiplying two binary numbers, U and V, of k bits or less, in a Galois field GF(2k), using a programmable circuit, comprising:
- a. choosing an irreducible polynomial of degree k, having coefficients of 1 or 0;
b. choosing a number m, less than k, which is no greater than the number of processing elements in the programmable circuit;
c. logically mapping functions that would be performed by an xth processor of a k-bit serial multiplier onto a yth processor of an m bit super-serial multiplier, where y=x mod m;
d. using the super-serial multiplier to emulate in ┌
k/m┐
cycles one cycle of the serial multiplier, thus multiplying one bit of U by V; and
e. repeating step d k times, each time appropriately combining the prior partial product with the results of the current multiplication, whereby the product of U and V is determined in k*┌
k/m┐
cycles.
7 Assignments
0 Petitions
Accused Products
Abstract
A scalable multiplier architecture for the Galois field GF(2k) is implemented in a programmable circuit. This architecture may be used in an implementation of public-key cryptosystems which use programmable multipliers in large Galois fields. This architecture is also fine grain scalable in both the time and the area (or logic) dimensions.
30 Citations
50 Claims
-
1. A method for multiplying two binary numbers, U and V, of k bits or less, in a Galois field GF(2k), using a programmable circuit, comprising:
-
a. choosing an irreducible polynomial of degree k, having coefficients of 1 or 0;
b. choosing a number m, less than k, which is no greater than the number of processing elements in the programmable circuit;
c. logically mapping functions that would be performed by an xth processor of a k-bit serial multiplier onto a yth processor of an m bit super-serial multiplier, where y=x mod m;
d. using the super-serial multiplier to emulate in ┌
k/m┐
cycles one cycle of the serial multiplier, thus multiplying one bit of U by V; and
e. repeating step d k times, each time appropriately combining the prior partial product with the results of the current multiplication, whereby the product of U and V is determined in k*┌
k/m┐
cycles.- View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. A method for programming a programmable circuit to multiply two binary numbers, U and V, of k bits or less, in a Galois field GF(2k), comprising:
-
a. choosing an irreducible polynomial of degree k, having coefficients of 1 or 0;
b. choosing a number m, less than k, which is no greater than the number of processing elements in the programmable circuit;
c. programming the programmable circuit wherein functions that would be performed by an xth processor of a k-bit serial multiplier are logically mapped onto a yth processor of the m bit super-serial multiplier, where y=x mod m;
d. programming the programmable circuit wherein the super-serial multiplier emulates in ┌
k/m┐
cycles one cycle of the serial multiplier, thus multiplying one bit of U by V; and
e. programming the programmable circuit wherein the process of step d is repeated k times, each time appropriately combining prior partial product with results of the current multiplication, whereby the product of U and V is determined in k*┌
k/m┐
cycles.- View Dependent Claims (13, 14, 15, 16, 17, 18, 19, 20, 21, 22)
-
-
23. A method for emulating the operation of a serial multiplier multiplying two binary numbers U and V, of k bits or less, in the Galois field GF(2k) in a programmable circuit, comprising:
-
a. choosing an irreducible polynomial of degree k, having coefficients of 1 or 0;
b. choosing a number m, less than k, which is no greater than the number of processing elements in the programmable circuit;
c. logically mapping functions that would be performed by an xth processor of the k-bit serial multiplier onto an yth processor of the m-bit super-serial multiplier, where y=x mod m; and
d. using the super-serial multiplier to emulate in ┌
k/m┐
cycles one cycle of the serial multiplier, thereby multiplying one bit of U by V.- View Dependent Claims (24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34)
-
-
35. A programmable circuit program to multiply two binary numbers, U and V, of k bits or less, in a Galois field GF(2k), comprising:
-
a. means for choosing an irreducible polynomial of degree k, having coefficients of 1 or 0;
b. means for choosing a number m, less than k, which is no greater than the number of processing elements in the programmable circuit;
c. means for logically mapping of functions that would be performed by an xth processor of a k-bit serial multiplier onto a yth processor of the m bit super-serial multiplier, where y=x mod m;
d. means for having a super-serial multiplier emulate in ┌
k/m┐
cycles one cycle of a serial multiplier, thereby multiplying one bit of U by V; and
e. means for repeating step d k times, each time appropriately combining a prior partial product with results of a current multiplication, whereby the product of U and V is determined in k*┌
k/m┐
cycles.- View Dependent Claims (36, 37, 38, 39, 40, 41, 42, 43, 44, 45)
-
-
46. A method for programming a programmable circuit to multiply two binary numbers, U and V, of k bits or less, in a Galois field GF(2k), comprising:
-
a. choosing an irreducible polynomial of degree k, having coefficients of 1 or 0;
b. choosing a number m, less than k, which is no greater than the number of processing elements in the programmable circuit;
c. programming the programmable circuit wherein functions that would be performed by the xth processor of a k-bit serial multiplier are logically mapped onto the yth processor of the m bit super-serial multiplier, where y=x mod m;
d. programming the programmable circuit wherein the super-serial multiplier emulates in ┌
k/m┐
cycles one cycle of the serial multiplier, thus multiplying one bit of U by V; and
e. programming the programmable circuit wherein the process of step d is repeated k times, each time appropriately combining the prior partial product with the results of the current multiplication, whereby the product of U and V is determined in k*┌
k/m┐
cycles;
f. programming the programmable circuit wherein each time step d is performed, processors 0 to m−
1 of the serial multiplier are first emulated, then processors m to 2m−
1 are emulated, and so on until all k processors are emulated,g. programming the programmable circuit wherein the super-serial multiplier includes 3*┌
k/m┐
bits of storage for the V operand, the multiplication result W and the coefficients of the irreducible polynomial P, such storage being used to restore the state of the processor being emulated,h. programming the programmable circuit wherein the super-serial multiplier including a mechanism to propagate results from one cycle of the serial multiplier to another, i. programming the programmable circuit wherein the super-serial multiplier first restores the state of the emulated serial processor, then computes a next partial result, then saves a new state, j. programming the programmable circuit wherein in a first multiplication cycle of the serial multiplication emulation W is initialized with a product uk−
1V(x),k. programming the programmable circuit wherein the super-serial multiplier includes a data transfer mechanism from processor m−
1 to processor 0, to emulate the connection between processors m−
1 and m, 2m−
1 and 2m, and so forth, in the serial multiplier, andl. programming the programmable circuit wherein the irreducible polynomial P(x) is a trinomial of the form xk+xr+1, where r is small compared to k.
-
-
47. A programmable circuit to multiply two binary numbers, U and V, of k bits or less, in a Galois field GF(2k), comprising:
-
a. means for logically mapping functions that would be performed by an xth processor of a k-bit serial multiplier onto a yth processor of an m bit super-serial multiplier, where y=x mod m, m being less than k, and being no greater than the number of processing elements in the programmable circuit;
b. means for choosing an irreducible polynomial of degree k, having coefficients of 1 or 0, c. means for using the super-serial multiplier to emulate in ┌
k/m┐
cycles one cycle of the serial multiplier, thus multiplying one bit of U by V; and
d. means for repeating step d k times, each time appropriately combining the prior partial product with the results of the current multiplication, whereby the product of U and V is determined in k*┌
k/m┐
cycles.- View Dependent Claims (48, 49, 50)
-
Specification