Talk:Finite field arithmetic

C programming example

I needed to implement a multiplication in the rijndael field, so I used the code from this wiki page. I figuered out, that this code does not work.

(For these who are curious, I replaced the multiplication by correct look up tables for special numbers. So I do not have a working version of gmul...) — Preceding unsigned comment added by 91.22.122.245 (talk) 22:07, 26 June 2015 (UTC)

Rijndael Galois field

Great minds think alike; I independently wrote almost the same material for Rijndael Galois field. Can you say merge? Samboy 10:59, 29 May 2005 (UTC)

Does the Rijndael's finite field section belong in this entry? Shouldn't this be moved in the entry of Rijndael? — Preceding unsigned comment added by Desnacked (talk • contribs) 00:20, 4 April 2011 (UTC)

Copyvio

Someone may observe that the material here bears a striking resemblence to some material on my web page. This is because I am allowing the relevant materal on that web page to be released under the GFDL license; there is no copyright violation going on. Keep in mind that I myself can place material form my web page in to articles; however if anyone else copies materials form my web page in to articles, it is a Copyvio. Samboy 20:24, 29 May 2005 (UTC)

what?

• By making a logarithm table of the finite field, and performing subtraction in the table. Subtraction of logarithms is the same as division.

this sounds like a brute force attack by an other name, am I wrong?

ADDED BY Paul NO. LOG(A) - LOG(B) = LOG(A/B) Meaning: A/B = EXP(LOG(A) - LOG(B)) Hence factor may be calculated as substraction of LOGs

Matrix Inversion Example

Can any one help me in finding the multiplicative inverse of ${\begin{bmatrix}1&0\\1&2\end{bmatrix}}$in $GF(2^{4})$ step-by-step?

Small oops

I noticed a small oops in the text: > 0x1b corresponds to the irreducible polynomial x8 + x4 + x3 + x + 1.

0x1b is x^4 + x^3 + x + 1. 0x11b (as mentioned int he original Rijndael texts) is the actual polynomial. Since the bit you left off is the x^8 bit it's pointless to add it, but the text itself is still incorrect.

Added by Paul: Yes, this is absolutely pathetic. 0x1b cannot be "x^8 + x^4 + x^3 + x + 1" because "x^8 + x^4 + x^3 + x + 1" was the polynomial that we used for generation of the field. "x^8 + x^4 + x^3 + x + 1" = 0.

Sum of all field elements

Please see Talk:Field (mathematics)#Sum of all field elements. —The preceding unsigned comment was added by 80.178.241.65 (talk) 20:27, 15 April 2007 (UTC).

Inadequate description of algorithm

The description of the multiplication is really weird (the description, not the algorithm). It would be easier to understand in pseudocode than in natural language:

• "an eight-bit product p": this is not clear, you should say that the product will be computed in a variable called $p$;
• "make a copy of a and b...": this is a call to a function with parameter $a$ and $b$;

etc., every line would be smaller and more meaningful in pseudocode. I cannot understand why someone would write an algorithm in pure natural language. —The preceding unsigned comment was added by 81.247.15.55 (talk) 17:15, 9 May 2007 (UTC).

Long division edit?

Should there be something else instead of
0100011010
^000000000
in the middle of the long division example? Like the divisor 100011011
Sohannin (talk) 19:19, 30 March 2008 (UTC)

Inversion

I would like to add another method of doing inversion. I attempted it a while ago, but it was for the specific case of a 2⁸ field, not the general case. In a 2⁸ field, you can calculate an inverse by calculating x²⁵⁴. Due to being a finite field, x²⁵⁴ is equivalent to x^-1. Calculating x²⁵⁴ can be done using e.g. exponentiation by squaring. (Inefficient, but useful for example in an embedded processor where small code size is more important than speed.) Anyway, I've described the specific case here. What is the general method for any finite field? Cmcqueen1975 (talk) 01:08, 24 October 2008 (UTC)

ANSWER: The inverse is in any case x^{p^n-2} due to the fundamental equation x^{p^n}=x holding in any finite field. See any book on finite fields, e.g. Lidl-Nieterreiter. So the limitation n=1 in the text should be removed. — Preceding unsigned comment added by Cavour1980 (talk • contribs) 12:16, 3 May 2013 (UTC)

Most hardware implementations for inversion involve mapping to isomorphic composite fields (aka sub-fields) performing the inversion within the mapped field, then mapping the result back to the original field. Some software implementations do this as well. See section 4.2 in Compact Rijndael Hardware Architecture pdf. There some requirements for mapped field to be isomorphic, map(a + b) = map(a) + map(b) and map(a · b) = map(a) · map(b), as explained starting at section 7.8.2, page 95 of Standford - Introduction to finite fields pdf. Rcgldr (talk) 18:06, 25 May 2020 (UTC)

For division by a constant, carryless multiply instructions, such as pclmulqdq on X86 (SSSE3), can be use for up to GF(2^64), using 3 pclmulqdq instructions and 1 or 2 xors. Rcgldr (talk) 18:06, 25 May 2020 (UTC)

For inversion of an array of bytes, pshufb can be used to essentially to do a parallel table lookup for 16 bytes (clmul) or 64 bytes (AVX512) at a time. Rcgldr (talk) 18:06, 25 May 2020 (UTC)

vulnerable to timing attacks?

Under "Program Examples" after the sample code it says: "Note that this code is vulnerable to timing attacks when used for cryptography." However, this code has nothing to do with timing. Remove that warning?

SmilingRob (talk) 11:41, 8 February 2009 (UTC)

The article is focused on cryptography, and the code given is vulnerable to a cryptographic technique called a timing attack. The warning is therefore relevant. JackSchmidt (talk) 20:55, 8 February 2009 (UTC)

what if we fixed the code so it doesn't have the vulnerability?

uint8_t gmul(uint8_t a, uint8_t b) {
    uint8_t p=0,hi_bit_set,counter;
    for(counter = 0; counter < 8; counter++) {
        p^=(b&1)*a;//equivalent to "if(b&1)p^=a;"
        hi_bit_set=a>>>7;
        a<<=1;
        a^=hi_bit_set*0x1b;//hi_bit_set is 0 or 1
        b>>=1;
    }
}

this code isn't vulnerable for timing attacks, it replaces "if(one_bit_check)x^=a" with "x^=one_bit_check*a" and if the loop is unrolled there will be no branches whatsoever in the code. 134.58.253.55 (talk) 09:23, 4 October 2011 (UTC)

Zech logarithm

Thsi article is too mushy. Needs tautening. Where is the Zech logarithm? Lam & McKay collected algorithms ACM No 469. 96.21.220.144 (talk) 15:18, 11 March 2010 (UTC)John McKay

Arithmetic over a finite field

The Zech logarithm needs publicity! See Collected algorithms Lam & McKay Algorithm 469, Comm. ACM, vol. 15, 699, (1973)

Finite fields are mathematics. Cryptography is an application.

96.21.220.144 (talk) 15:16, 11 March 2010 (UTC)John McKay

The writer is confused. The notion of primitive is attached to a root that generates the multiplicative part of the field Fq. This root has order q-1. The polynomial of which it is a root is a primitive irreducible polynomial. The Rijndael remarks should be unxer Rijndael - they are not appropriate here in my view. 96.21.220.144 (talk) 21:39, 4 April 2010 (UTC) John McKay

Apparent contradiction

From the statement:

Elements of GF(p^n) may be represented as polynomials of degree strictly less than n over GF(p).

Then the examples for GF(2^8) show polynomials which include x^8 as the leading term. Shouldn't these examples then be labeled as GF(2^9) ? —Preceding unsigned comment added by 98.225.79.4 (talk) 00:23, 5 May 2011 (UTC)

The article is correct. The reducing polynomial has the x^8 term. Notice the two multiplicands used in the example are of degree less than 8: (x⁶ + x⁴ + x + 1) and (x⁷ + x⁶ + x³ + x), corresponding to 0x53 and 0xCA.--129.188.33.26 (talk) 18:54, 12 September 2012 (UTC)

Range of the modulo remainder?

If I calculate the remainder of an integer division by n the remainder is in the range 0…(n-1), so the remainder is always smaller than the divisor. What is the range of the remainder for polynomial divisions for a given polynomial $P(x)$? Is the remainder also always smaller (in degree or its coefficients) or not? Neither this article (for finite fields) nor the article Polynomial long divisions answer this question. :-/ --RokerHRO (talk) 06:03, 3 April 2012 (UTC)

The polynomial division reduces the degree. For example x^n = (1) * (x^n+x+1) + (-x-1) The quotient is thus 1 and the remainder -x-1. There is no such thing as a natural order between polynomials of same degree (is x^3-x greater than x^3+1 ?) Aka.nice (talk) 16:48, 20 August 2012 (UTC)

Show me that this is not nonsense

I have pulled this section from the article.

=== Primitive finite fields ===

A finite field is considered a primitive finite field if the element ("polynomial") x is a generator for the finite field. In other words, if the powers of x assume every nonzero value in the field, it is a primitive finite field. As it turns out, the GF(2⁸) finite field with the reducing polynomial x⁸ + x⁴ + x³ + x² + 1 is not primitive, although x + 1 is a generator in this field. The GF(2⁸) finite field with the reducing primitive polynomial x⁸ + x⁴ + x³ + x² + 1, however, is a primitive field.

Primitive finite fields are used, for example, by Linear feedback shift registers.

I have never seen the term primitive used in this manner. The penultimate sentence contradicts the one before it. There are no references. Before this is put back, it needs a lot of work, to say the least. Someone should consider redoing the entire page without the clunky polynomial representation of finite fields ... using the fact that the non-zero elements form a cyclic group makes multiplication and division trivial operations in finite fields. Bill Cherowitzo (talk) 04:43, 3 June 2013 (UTC)

@Wcherowi: Should have left that section, but fixed it, x⁸ + x⁴ + x³ + x + 1 is not primitive, as x is not a primitive element of that field, while x⁸ + x⁴ + x³ + x² + 1 is primitive, as x is a primitive element of that field. The terminology is correct. Every finite field has multiple primitives, for GF(2^8), typically 128 of of them, but if one of those primitives is x, then the field polynomial is considered primitive. Using GF(2^8) as an example, there are 30 irreducible polynomials of degree 8, 16 of which are also primitive. Rcgldr (talk) 19:32, 26 May 2020 (UTC)

Thanks for correcting that statement, however I still stand by my claim. The term "primitive finite field" does not appear in the mathematical literature, although it might in the CS literature. There are primitive elements and primitive polynomials, each of which is standard and well defined but the term "primitive finite field" would need a citation.--Bill Cherowitzo (talk) 19:59, 26 May 2020 (UTC)

Your recent edit included a reference, but the term "primitive finite field" does not appear in that citation. Try again.--Bill Cherowitzo (talk) 22:17, 26 May 2020 (UTC)

I edited the section so that it now refers to the finite field polynomial as being primitive. The term "primitive finite field" is used in some literature as a short hand term for "finite field with primitive polynomial". Note that there are other mathematically oriented definitions for primitive polynomial where it is not clear that it translates into x being a primitive element of a polynomial. One key point of this is using a primitive polynomial generally reduces gate count for hardware implementations, and depending on how software is implemented there is benefit there. There's no benefit in software if the math relies on tables for multiply, divide, and/or exponentiation. Rcgldr (talk) 23:17, 26 May 2020 (UTC)

I am sorry that I sent you off on a wild goose chase. I know that the term "primitive finite field" does not exist, even as a shorthand for something else. Every finite field has primitive polynomials and/or primitive elements, so the descriptor is meaningless. The problem here is that having x as a primitive element is not a property of the field, but only a property of this representation of the field. The article section still needs some copyediting, for instance, "reducing polynomial" is a CS term and has not been defined and it has to be made clear that there are several representations of the field all of which are isomorphic.--Bill Cherowitzo (talk) 17:40, 27 May 2020 (UTC)

I've seen the term "primitive finite field" or even just "primitive field" used in professor's notes for several CS courses on error correction codes, mostly Reed Solomon codes. For a finite field such as GF(p), where p is a prime number, x doesn't exist as an element of the field. You need GF(p^m) with m > 1 in order to have x as an element of the field. I used the term "reducing polynomial" because it was already used in the article: "Multiplication in a finite field is multiplication modulo an irreducible reducing polynomial" Finite_field_arithmetic#Multiplication. Again short hand for "The field of polynomials over GF(p) modulo an irreducible polynomial of degree m is called the Galois field of p^m elements, or GF(p^m)". In the case of a sub-field, due to using a non-primitive element, x may not exist in the sub-field. "All fields are isomorphic" - In the case of Finite_field_arithmetic#Composite_field, if math operations (addition and multiply) are to be consistent between the two fields, a mapping function has to be generated to comply with the constraint that while operating in the alternate field, map(a + b) = map(a) + map(b) and map(a · b) = map(a) · map(b). The inverse mapping would also have the same constraints. Using α to represent a primitive element of the original field, and β to represent a primitive element of the alternate field. Then β^j = map(α^j) and α^j map^-1(β^j). Typically β is chosen to optimize the math and a search is done for any α that will meet the constraints. Note this same strategy could be used to map between two fields GF(p^m) that are defined by two different irreducible polynomials, but this would not normally result in optimizing of math operations, except possibly in the case where some form of hardware based implementation is to be used to perform math on a field based on a different polynomial. Rcgldr (talk) 21:21, 27 May 2020 (UTC)

Thanks for the update to the primitive polynomial section. Rcgldr (talk) 21:14, 27 May 2020 (UTC)

• - Note that Finite_field_arithmetic#Multiplication is using the term "reducing", should it just be deleted or replaced? Rcgldr (talk) 21:24, 27 May 2020 (UTC)

No need. I've introduced the term in the earlier section. Professors can sometimes get sloppy in their own notes (I know that I have on occasion been known to do so) and use terminology that they wouldn't use in print. --Bill Cherowitzo (talk) 22:01, 27 May 2020 (UTC)

Code Examples

The C# version has being replaced by a D language version that I think is more explicit (instead of a hex number it uses the base 2 literal 0b1_0001_1101, is more easy to see it stands for x^8 + x^4 + x^3 + x^2 + 1. It has function annotations that tag the function as pure and not throwing, it doesn't contain a cast because the D compiler is able to infer that a & 0x80 is an unsigned byte (where a is the same)).

The code also generates a 256x256 grey scale image that I think it's worth adding to this article (regardless if you want to keep the D code or not). — Preceding unsigned comment added by 79.27.201.211 (talk) 09:42, 29 June 2013 (UTC)

D is not a widely used language and therefore may be difficult for some people to understand. We should change it back. NessThePSIKid (talk) 00:23, 28 September 2017 (UTC)

Extended Finite Field

In many text, when n=1, it is called Finite Field, and when n>1, it is called extended Finite Field. By the way, the characteristic mentioned in the article is just the p used in the article. Becaseu Wcherowi reverted what I edited, so I put it here. Jackzhp (talk) 10:39, 4 January 2018 (UTC)

If you think that this usage appears in many texts, then you should have no difficulty providing references that demonstrate it. Common usage is that the finite fields where n = 1 are called prime fields, the other finite fields (where n > 1) may be considered extensions of the prime fields, but the term "extended finite field" is clearly false in reference to them. --Bill Cherowitzo (talk) 21:26, 4 January 2018 (UTC)

The terminology I usually see is "prime field" when n=1, and "non-prime field" when n≠1. There aren't a lot of implementations of prime fields, with the main exception being GF(929), as used for PDF-417 bar codes, which is shown in the example decodings in Reed Solomon. Rcgldr (talk) 23:35, 26 May 2020 (UTC)

Examples of composite field mapping

I am not proposing this be added to the article. If anyone is interested, this is an example of how to generate the matrices to map between GF(2^8) and a composite field GF(((2^2)^2)^2). For this particular case, all but one of the parameters is fixed, and the one variable parameter, a primitive element of GF(2^8) that meets the constraints as explained in the document (map(a + b) = map(a) + map(b), and map(a b) = map(a) map(b)), is found by brute force search by trial and error using the mapping matrices which are generated based on the primitive elements of GF(2^8) (to be determined by search) and GF(((2^2)^2)^2) (a given fixed value) until a primitive element of GF(2^8) is found that meets the requirement. Doing a similar search for a primitive element of larger field, such as mapping GF(2^32) to GF((2^16)^2) would require a "smarter" search to reduce the time it takes for the search. Composite Field Mapping Example pdf Rcgldr This mapping example uses the mapping matrices seen on page 4, matrix (8) and page 5, matrix (10) of A reference implementation of the AES S-Box pdf

Link to a 1995 report by professor E J Weldon Jr, showing a mapping from GF(2^8) to GF((2^16)^2) used to reduce gate count for inversion (1/x) in GF(2^8) by mapping to GF((2^16)^2), doing some algebra in GF((2^16)^2), and mapping back. In this case, the primitives of both GF(2^8) and GF((2^16)^2) are x + 0, so no searching for primitive elements in either field is needed. Since then, gate count has been further reduce by mapping to GF(((2^2)^2)^2), which gets back to having to search for a primitive element of GF(2^8). E J Weldon Jr report Rcgldr (talk) 04:49, 27 May 2020 (UTC)

Implementation tricks - pshufb (xmm) vpshufb(zmm)

These instructions do parallel table lookups for 16 bytes (pshufb, xmm, SSSE3) or 64 bytes (vpshufb, zmm, AVX512) at a time. This can be used for something like multiply an array of GF(2^8) bytes by a constant, 16 or 64 bytes at a time. The lookup operation is limited to 4 bit indexes (6 bit indexes for zmm registers, but only 4 bit indexes would be used for GF(2^8) multiply by constant). The pshufb operation can be described as for i = 0 to n-1, destination register byte[i] = destination register byte [index register byte[i]], but done in one parallel operation. The bytes of a register are indexed right (least significant) to left (most significant). The indexes don't have to be unique: if all of the indexes in the index register are the same, then the same index is used to copy one byte of the destination register into all 16 or 64 bytes of that register. For a 64 byte zmm register, since only 4 bit indexes are used, the indexing only reads from the low order 16 bytes of the destination register, but reads all 64 bytes of the index register and writes all 64 bytes of the destination register. The constant multiplier is used to index a table to load two registers with 16 bytes of lookup data: one is for the constant times the lower 4 bits of a data byte, the other for the constant times the upper 4 bits of a data byte. A block of 16 or 64 bytes of data is loaded into a register, copied into a second register. One register is masked so that register holds the lower 4 bits of each data byte. The other register is masked and shifted right so it holds the upper 4 bits of each data byte shifted right 4 bits. These two registers will be used for indexing. The two registers with table data are copied into two registers which will end up with the indexed data. For the low order register, pshufb copies the low order lookup table values in that register back to that register according to the indexes in the low order index register. The same is done for the high order register, and then those two registers are xor'ed to produce the 16 or 64 byte products. The xmm/zmm register operations can overlap if there aren't conflicts. For the 16 xmm registers, 4 are needed for masks and constant multiplier, 4 are needed for each 16 bytes of data, so data could be processed 48 bytes at a time. For the 32 zmm registers, 448 bytes could be processed at a time. Intel provides a general description of this concept for AES encryption, and I can produce other references, but this may be too complicated for the Wiki article. Rcgldr (talk) 14:54, 28 May 2020 (UTC)

Rijndael's (AES) finite field example

The example includes the following: = {3F7E mod 11B} = {01}

Some explanation is needed since in ordinary modular arithmetic 3F7E mod 11B = 7B. So either the reduction should be explained clearly, or the hexadecimal representation is misleading.

The math is "binary" math where the subtractions steps of a long hand division are implemented as XOR. Rcgldr (talk) 17:33, 10 December 2020 (UTC)

Right, the math is on binary polynomials, not integers. The hexadecimal representation is not helpful. I suggest removing it.

Technically correct, but there's no reason not to define binary math operations such as XOR (to replace addition and subtraction), carryless multiply, and borrowless divide which operate on integers. Carryless multiply is an instruction implemented on X86 (pclmulqdq) and other processors, and generally the instructions description define the operands as integers, not polynomials. Rcgldr (talk) 16:51, 11 December 2020 (UTC)

That is all true, but does not address the point about hexadecimal representation. The previous line in the artice reads: = (11111101111110 mod 100011011). That is perfectly fine, since the article until now has been talking about representing polynomials in binary form. The next line is disconnected from the article until this point by introducing an irrelevant and confusing hexadecimal representation. It simply doesn't help understanding. Eddywiki78 (talk) 08:02, 15 December 2020 (UTC)

@Eddywiki78: Hexadecimal representation is explained near the beginning of the article: Effective polynomial representation Rcgldr (talk) 16:39, 30 December 2020 (UTC)

Composite fields - polynomial basis, normal basis

I'm wondering if this should be added to the composite field section. Consider the case of mapping from GF(2⁸) to GF(((2²)²)²). With polynomial basis, a composite field element for GF(2²) can be defined as (a w + b), where a and b are 1 bit elements of GF(2) and w is a variable of GF(2²). With normal basis, the composite field for GF(2²) can be defined as (a W² + b W), where a and b are 1 bit elements of GF(2) and W is an element of GF(2⁸). With polynomial basis, a composite field element for GF(((2²)²)²) can be defined as (e y + f), where e and f are 4 bit elements of GF(2⁴) and y is a variable of GF(((2²)²)²). With normal basis, a composite field element for GF(((2²)²)²) can be defined as (e Y¹⁶ + f Y), where e and f are 4 bit elements of GF(2⁴) and Y is an element of GF(2⁸). Link to an example article: A very compact Rijndael S-box. I added some more details about that article in this post. Rcgldr (talk) 08:24, 29 December 2023 (UTC)