Processing Galois Field arithmetic

Details Processing Galois Field arithmetic Processing Galois Field arithmetic

2001-05-08

2004-07-20

Mai, Tan V. (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

06766344

ABSTRACT:

FIELD OF THE INVENTION
The invention relates to processing algorithms involving Galois Field arithmetic and relates particularly, though not exclusively, to the efficient execution of algorithms involving Galois Field arithmetic, as typically found in communications and cryptography applications.
BACKGROUND
A Galois Field is a finite set of elements in which addition, subtraction, multiplication and division (all appropriately defined) can be performed without leaving the set. Addition and multiplication must satisfy the commutative, associative and distributive laws. Galois Field arithmetic finds wide use in a variety of engineering applications, including error correcting codes and cryptography. For a concise and comprehensive exposition of Galois Fields, refer to Lidl and Niederreiter,
Introduction to Finite Fields and Their Applications
, Cambridge University Press, Cambridge, Mass., 1986.
In view of the varied applications noted above, there has been considerable attention given to efficient methods and apparatuses for Galois Field computations. In this respect, U.S. Pat. No. 5,689,452 issued to Cameron on Nov. 18, 1997 discloses a programmable digital computer with special-purpose logic units to efficiently perform Galois Field arithmetic. Cameron discloses a method of decoding Reed-Solomon codes in a large Galois Field GF(2
n
) in which the finite field is represented as a quadratic extension field of one or more subfields GF(2
m
). Basic arithmetic operations in the extension field are written solely in terms of operations performed in one or more subfields. Multiplicative operations performed in GF(2
n
) use only operations from GF(2
m
).
There have also been attempts to efficiently perform Galois Field arithmetic on general-purpose wide-word computers. A wide-word computer with a W-bit word can be looked upon as a SIMD (single instruction, multiple data) computer capable of operating upon one or more sets of k operands, each (W/k) bits wide, simultaneously with a common instruction. Computers with such architectures can be used to efficiently perform several computations in parallel and, accordingly, there are potential efficiency advantages that may be exploited. However, existing SIMD architectures are not ideally suited to performing Galois Field arithmetic as such architectures are not able to effectively perform operations typically associated with data manipulations executed when computing Galois Field operations.
Despite the work referred to above, there are limitations associated with existing techniques. Accordingly, a need clearly exists for a method . . . at least attempt to address these and other limitations associated with such techniques.
SUMMARY OF THE INVENTION
It is recognised that efficient parallel processing of algorithms involving Galois Field arithmetic can be achieved using an appropriate decomposition into corresponding operations in selected subfields.
Accordingly, a first aspect of the invention provides a method for processing algorithms involving Galois Field arithmetic suitable for execution by digital hardware able to process k-bit operands. This involves mapping source arithmetic operations in Galois Field GF(2
n
) into respective sets of corresponding arithmetic operations for a plurality of isomorphic composite Galois Fields GF((2
p[1]
)
p[2]
) . . . )
p[v]
), for each of which &pgr;
v
i=1
p[i]=n.
For each respective set of corresponding operations, a cost function relating to an implementation of the source arithmetic operations with the set of corresponding arithmetic operations is evaluated. As a result, one of the sets of corresponding arithmetic operations is selected as a target set of arithmetic operations, based on the calculated results of the cost function for each of the respective sets. Further, the source arithmetic operations of Galois Field GF(2
n
) are converted to the target set of arithmetic operations of the respective isomorphic composite Galois Field, the target arithmetic operations having k-bit operands.
In the described embodiment, the technique of data-slicing is used in combination with the mathematical technique of mapping arithmetic operations of the field GF(2
n
) in terms of operations in appropriately chosen subfields of GF(2
n
). Described embodiments enable Galois Field arithmetic to be effectively executed with SIMD computing architectures with relative efficiency and speed. An efficient implementation for any algorithm with Galois Field arithmetic can be derived where significant data-parallelism exists. Two examples of such an algorithm are Reed-Solomon decoders (generally described in Lin and Costello,
Error Control Coding
, Prentice Hall; ISBN: 013283796X, October 1982), and the recently selected Rijndael proposal for private key (symmetric key) cryptography.
Though there are advantages associated with implementing the described method with a data-sliced arrangement, such methods can also be executed on existing SIMD or non-SIMD architectures. The described methods are not restricted to the preferred Galois Field computer hardware architecture described herein, though there is a clear performance benefit available as the efficiency of the method depends on the architecture used.
The aspects of the invention attempt to provide an efficient implementation of applications involving Galois Field arithmetic in which there is the potential to exploit data parallelism with by performing relevant calculations with relatively greater computational efficiency.


REFERENCES:
patent: 5689452 (1997-11-01), Cameron
patent: 6581180 (2003-06-01), Weng
patent: 2002/0157059 (2002-10-01), Gregori et al.
Lidl and Niederreiter, “Introduction to Finite Fields and Their Applications”, Cambridge University Press, Cambridge, MA, 1986, pp. 1-69.
Christof Paar, “Efficient VLSI Architectures for Bit-Parallel Computation in Galois Fields”, Sections 2.1.2 and 2.2, PhD Thesis, Instituts for Experimental Mathematics, University of Essen, Germany, 1994.
John Daemen and Vincent Rijmen, “AES Proposal: Rijndael”, available from Computer Security Resource Center, US National Institute of Standards and Technology, http:\\csrc.nist.gov, Sep. 1999.
Eli Biham, “A fast new DES implementation in Software”, Technical Report CS0891, Computer Science Department, Technion-Israel Institute of Technology, 1997, 13 pages.
M.J. Flynn, “Very high-speed computing systems”, Proc. of the IEEE, vol. 54, 1966, pp. 1901-1909.
A. Peleg and U. Weiser, “MMX Technology Extension to the Intel Architecture”, IEEE Micro, Jul./Aug. 1996, pp. 42-50.
K. Diefendorff, P. Dubey, R. Hochsprung, and H. Scales, “AltiVec Extension to Power PC Accelerates Mediaprocessing”, IEEE Micro, Mar./Apr. 2000, pp. 85-95.
Lin and Costello, “Error Control Coding”, Prentice Hall, ISBN:013283796X, Oct. 1982, Chapter 6, pp. 170-176.
C.S. Jutla, “Encryption Modes with Almost Free Message Integrity”, Computer Security Resource Centre, US National Institute of Standards and Technology, First Modes of Operation Workshop, Baltimore, MA, Oct. 20, 2000, 6 pages, http\\csrc.nist.gov/CrypoToolkit/modes/workshop1/papers/jutla-auth.pdf.

Affiliated with

Also associated with

Rating

Processing Galois Field arithmetic does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Processing Galois Field arithmetic, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Processing Galois Field arithmetic will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3239347