Talk:Finite field

Proposal to add a section for isomorphisms aka composite fields aka sub-field mapping

I feel there should be a section about composite fields. A common example is mapping of GF(2^8) to GF(((2^2)^2)^2) for inversion (1/x) of a GF(2^8) number for AES encryption hardware where there may be 10 or more encoders/decoders on a single card, and the composite field greatly reduces gate count. Prior to carryless multiply instructions, composite fields allowed for faster computations for GF(2^32) and larger fields. However, with the carryless multiply pclmulqdq instruction on a X86 (since 2008), a GF(2^32) or GF(2^64) multiply can be done with 3 pclmulqdq and 1 or 2 xors. Rcgldr (talk) 22:58, 23 May 2020 (UTC)

There is also some little known information that should be archived somewhere, such as if a primitive field is going to be mapped to a primitive composite field, both using the standard primitive element x+0, then the larger field polynomial with coefficients changed to be the smaller fields coefficient size will have factors that correspond to the mappable fields (using alternate primitives allows for more flexible mapping). For example, for GF(2^32) = x^32 + ^x^22 + x^2 + x + 1 mapped to GF((2^16)^2) x^2 + ax + b with GF(2^16) coefficients based on x^16 + x^12 + x^3 + x + 1, if GF(2^32) polynomial reinterpreted as GF((2^16)^32) = x^32 + ^x^22 + x^2 + x + 1, then the 16 factors of GF((2^16)^32) in the form x^2 + ax + b, will be the mappable polynomials (out of a possible 4 billion). Rcgldr (talk) 22:58, 23 May 2020 (UTC)

How the matrices used to map between a primary field and a composite field are generated is difficult to find. Rcgldr (talk) 23:01, 23 May 2020 (UTC)

Can you point to any appropriate sources that discuss this? (At the level of mathematics, the objects GF(2^8) and GF(((2^2)^2)^2) are not different, though obviously the second notation emphasizes a particular idea of building it by three quadratic extensions. It seems plausible that there might be advantages of one representation versus another in CS, but we need reliable sources for that.) —JBL (talk)11:21, 24 May 2020 (UTC)

As mentioned above, there's been a lot of effort put into reducing gate count for AES S boxes, via GF(2^8) to GF(((2^2)^2)^2). Example references: GF(((2^2)^2)^2)(AES) S-box , A Very Compact S Box pdf. Other examples are about reducing large fields GF(2^n) for n >= 32: Efficient Software Implementations of Large Finite Fields pdf, which describes mapping GF(2^32) to GF((2^16^2), defines GF((2^16^2) and GF(2^16), but doesn't define GF(2^32) (it's probably jerasure standard x^32 + x^22 + x^2 + x + 1), and doesn't define the mapping matrix or it's inverse. I had to do an optimized brute force search to determine the missing data, to answer a question at a forum GF(2^32) to GF((2^16)^2) mapping. Rcgldr (talk) 12:50, 24 May 2020 (UTC)

As for generating mapping matrices, let k = m · n, and GF(2^k) is to be mapped to GF((2^m)^n). Let e = the number of elements to map at a time, formatted as a matrix, elements[k][e]. Define the GF(2) mapping matrix as map[k][k]. Mapping e elements from GF(2^k) to GF((2^m)^n) is done via map[k][k] x elements[k][e]. The inverse of map is used to map back. The column indexes (right to left) of map[][] correspond to bit indexes of elements, map[][{...,4,3,2,1,0}] correspond to element bits {...,4,3,2,1,0}. Let α(x) = a primitive element of GF(2^k), and β(x) = a primitive element of GF((2^m)^n). The column values of map[][{...,4,3,2,1,0}] are pow(β(x),log_α(x)({...,16,8,4,2,1})). I'm looking for a reference for this, but generally the articles I find assume the reader is aware of this and just show an image of the k by k bit matrix. Rcgldr (talk) 12:50, 24 May 2020 (UTC)

For a given GF(2^k), GF((2^m)^n) has to be determined to follow two basic rules. Let a and b be elements of GF(2^k), then while operating in GF((2^m)^n) map(a + b) = map(a) + map(b) and map(a · b) = map(a) · map(b). In the case where α(x) = x + 0 and β(x) = x + 0, GF((2^m)^n) can be any of the m factors of GF(2^k) reinterpreted to have coefficients of GF(2^m), essentially GF((2^m)^k). For better optimization, α(x) can be any primitive element of GF(2^k), and an optimized brute force for the "best" combination of α(x) and GF((2^m)^k) is done. This is described in the paper I linked to before: A Very Compact S Box pdf. Rcgldr (talk) 12:50, 24 May 2020 (UTC)

As far as I understand your post, you are concerned by computation is finite fields. For this, a representation of the field is needed, either as polynomials over GF(2) modulo an irreducible polynomial, or as a tower such representations. Your problems seems 1/ to determine the representation that leads to the most efficient computation 2/ (possibly) getting efficient algorithms for changing of representation. Both problems could be considered in the article (for the representation by a simple extension, the best choice of the defining polynomial is already sketched (with a reliable source) in section "non-prime field". For describing the known solutions of the other problems, we need sources. Those that you provide are not convenient for Wikipedia, as they are original research and consist mainly in proposed solutions, and they do not provide any synthesis of the knowledge in the subject. We need absolutely such a synthesis because, otherwise the presentation would be biased by giving emphasis to results for which we do not know whether they are generally accepted solutions. This is for this reason that original research and original syntheses are forbidden in Wikipedia (see WP:OR). As this subject seems to evolve rather quickly, this seems to early for presenting it in WP. D.Lazard (talk) 17:55, 24 May 2020 (UTC)

"Too early?" - there have been hardware implementations of composite (sub-field) mapping since the 1990's. I have a 1995 report from E J Weldon Jr for implementing hardware inversion (1/x) for GF(2^8) x^8+x^7+x^2+x+1 (hex 187, a primitive polynomial) using composite field (AKA sub-field mapping AKA "residue over a polynomial of degree 2 over GF(2^4)"). Usage of composite fields was fairly well known by the people involved in Reed Solomon codes or AES encryption by that time and probably dates back another 5 to 10 years prior to that report. In his 1995 report, he describes a mapping to GF((2^4)^2) x^2 + 4x + 2. Other implementations further reduced gate count by mapping to GF(((2^2)^2)2) and using a quadratic of the form x^2 + x + c. Some of the references in A Very Compact S Box pdf should qualify as reliable sources. Rcgldr (talk) 09:20, 25 May 2020 (UTC)

Again, the references that you provide do not allow writing the section that you are asking for, without doing WP:original synthesis. By "too early", I meant that we must wait a published synthesis on the subject, which is apparently still lacking. D.Lazard (talk) 09:41, 25 May 2020 (UTC)

I still am not getting what you mean by published synthesis. As for the algorithms and math involved, the articles are not lacking. The articles are out there, and I'm currently looking for such articles. I've found a few which I've posted below. Rcgldr (talk) 03:55, 26 May 2020 (UTC)

Here is a link to a portion of that report by professor E J Weldon Jr Finite Field Isomorphisms - Inversion pdf. I found more complete examples and explanations of using isomorphism for calculating a multiplicative inverse in GF(2^8). Starting at section E in aes sbox pdf and section 4.2 in Compact Rijndael Hardware Architecture pdf. Perhaps this should be also be added to Finite field arithmetic#Multiplicative inverse Rcgldr (talk) 16:56, 25 May 2020 (UTC)

Composite or sub-mapped fields are isomorphic in addition and multiplication: map(a + b) = map(a) + map(b) and map(a · b) = map(a) · map(b). This is explained starting at section 7.8.2, page 95 of Standford - Introduction to finite fields pdf. For binary field mapping of the form GF(2^k) to GF((2^m)^n), generally GF(2^k) is fixed, the parameters for GF((2^m)^n) are pre-selected, and a search is done for a primitive element of GF(2^k), which is used to generate the mapping matrix, so that the resulting field GF((2^m)^n) is isomorphic to GF(2^k) in addition and multiplication. In the case of minimizing gate count for a given GF(2^8) such as AES x^8 + x^4 + x^3 + x + 1, nested mapping may be used, such as GF(2^8) to GF(((2^2)^2)^2), and a search for a primitive element of GF(2^k) as well as some of the constants for GF(((2^2)^2)^2) is done to result in a minimal gate count. This is the focus of the "very compact s box" articles. Rcgldr (talk) 03:55, 26 May 2020 (UTC)

I now think this would be more appropriate in Finite field arithmetic, since the purpose is to optimize mathematical operations on finite fields. I'm dropping the proposal for here. Rcgldr (talk) 00:45, 27 May 2020 (UTC)

Notation

I'd like to propose that the article favor the notation $\mathbf {F} _{q}$ over the older and more cumbersome $\operatorname {GF} (q)$. Both are used in the literature, so of course both should be mentioned in the article, but the current editions of most books by experts (Artin, Bourbaki, Lang, Serre, etc.) use $\mathbf {F} _{q}$, so it would be good if Wikipedia followed suit by using $\mathbf {F} _{q}$ in most places, while mentioning $\operatorname {GF} (q)$ as an alternative notation. Ebony Jackson (talk) 19:52, 13 December 2020 (UTC)

IMO, notation $\mathbf {F} _{q}$ should be discarded in favour of $\mathbb {F} _{q}$ and $\operatorname {GF} (q).$ The reason is that contrary to the two other notations, $\mathbf {F} _{q}$ is ambiguous as it may denote an indexed variable (boldface is often used for variables representing vectors or matrices). When reading an article that does not define its notations, if one encounters $\mathbb {F} _{q}$ or $\operatorname {GF} (q)$, one knows immediately that this denotes a finite field. On the contrary, with $\mathbf {F} _{q}$ one needs to look at the context. So, $\mathbf {F} _{q}$ should be mentioned only for completeness.

This is true that $\mathbb {F} _{q}$ is more commonly used in pure mathematics and number theory. On the other hand, $\operatorname {GF} (q)$ is more commonly used in computer science. This is mainly for historical reasons, but a practical reason exists also: in pure mathematics, q is generally a variable or a small integer, while in computer science, q is often an explicit number involving an exponent or a double exponent, which makes cumbersome to use q as an index: compare $\mathbb {F} _{2^{64}}$ and $\operatorname {GF} (2^{64})$ (this is the largest field whose elements can be represented by double machine words). I have rewritten this article some time ago, and if I have preferred the notation $\operatorname {GF} (q),$ this is mainly because the notation had to be used in section headings. Otherwise, because of my personal history, I would have preferred $\mathbb {F} _{q}.$

So, both notations are widely used in recent literature, and Wikipedia policy is that, in such a case, it is not to Wikipedia to establish rules. D.Lazard (talk) 21:43, 13 December 2020 (UTC)

I am inclined to agree that this is a difference between fields, rather than eras -- in my experience, GF(q) is the most common notation in the coding theory literature, for example, while it seems not to be used at all in algebraic combinatorics. --JBL (talk) 22:08, 13 December 2020 (UTC)

I agree with JBL. Having taught a wide spectrum of courses that use finite fields, I have had to use both notations, depending on the subject and text. As a finite projective geometer, I have used the $\operatorname {GF} (q)$ notation almost exclusively, as that is the standard in this area. On a totally practical note, I prefer this notation since the exponents (and that is where all the action is ) are typeset in a slightly larger font, making them easier to read.--Bill Cherowitzo (talk) 23:31, 13 December 2020 (UTC)

OK, thank you all; you have convinced me to withdraw my proposal. By the way, the "Extensions" section at the end of the article uses the $\mathbf {F} _{q}$ notation; should that be changed for consistency? Ebony Jackson (talk) 06:03, 16 December 2020 (UTC)

It seems that the algebraic closure of a finite field is never considered in areas denoting finite fields by GF(q). So it seems better to not use this notation in this section. However I am in favour to change systematically $\mathbf {F} _{q}$ into $\mathbb {F} _{q},$ and to use $F$ instead of $\mathbf {F}$ when there is no subscript. D.Lazard (talk) 11:07, 16 December 2020 (UTC)

OK, done. Ebony Jackson (talk) 03:23, 17 December 2020 (UTC)

I have just read this. I apologize for effectively undoing the $\mathbf {F} _{q}$ to $\mathbb {F} _{q}$ notation changes, and will be happy to conform the notation to the suggestion again. Some questions, though:

• Isn't it inconsistent if we do not simultaneously use $\mathbb {Z}$, for instance? I assume that would be changed too.
• I consider the Unicode blackboard bold characters to be problematic on some browsers, so I would stick to inline <math> as it was and not use Unicode characters. Is the mix of <math>, {{math}} not an issue, i.e. should we change everything to <math>?

—Quondum 23:58, 4 January 2021 (UTC)

Either $\mathbb {Z}$ or $\mathbf {Z}$ is OK for me, though I guess you are right that if we are writing $\mathbb {F} _{q}$ as D.Lazard preferred, then it would make sense to write $\mathbb {Z}$ too, for consistency. For other symbols other than these blackboard bold letters, however, I think it would be OK to leave them inside the math template if they look OK as they stand. I do think that that template looks a little better, for simple formulas. Ebony Jackson (talk) 01:46, 5 January 2021 (UTC)

Sorry about the parsing (now with a quick fix applied) – an early preview actually showed that construction working.

Okay, I'll wait for any other comments. They whole font/rendering thing in WP maths has been an issue for ever so long that hoping for some "perfect style" is a bit of a dream. —Quondum 02:54, 5 January 2021 (UTC)

Concrete simple worked out example

@Cirosantilli2: [Normally, the talk pages work FIFO (First In First Out), which means that the latest sections are at the bottom.]

I tried to improve didactic but it was reverted: https://en.wikipedia.org/w/index.php?title=Finite_field&type=revision&diff=1044934168&oldid=1044905041 It is a shame that the first Google hit for a mathematics subject is often not the one you can actually learn mathematics subjects from. Cirosantilli2 (talk) 08:33, 18 September 2021 (UTC)

@Cirosantilli2: To your edit on 17:37, 17 September 2021‎:

Your first sentence

$4=2^{2}$, so one way to represent the elements of the field will be the to use the 4 polynomials of degree 1 over GF(2):

• 0X + 0
• 0X + 1
• 1X + 0
• 1X + 1

is blatantly wrong. First: I do not understand what "the to use the 4 polynomials of degree 1" means? Can't you be more careful in your wording? Second: if you mean polynomials in X (which is highly probable) then I see 2 of degree 0 and 2 of degree 1. But you improve didactically to 4 of degree 1. Third, the sentences after "Addition is defined element-wise with ...": I can't see a didactical gain in falling back from the variable α (which was already in the text and which is maintained by you) to the indeterminate X (with absolutely the same arithmetic principles, but α much more easily to understand and to calculate with).

What you can learn from your contribution is: that (although you thought, I "can actually learn mathematics subjects from") I was totally unable to learn something from it. It is misleading to me and I'm sure to other people, too. Hopefully, you are able to learn from it – in some sense – as well !

With my best wishes and regards, –Nomen4Omen (talk) 14:12, 18 September 2021 (UTC)

Nevertheless, Cirosantilli2 edit reveals an issue in this section: A good encyclopedic tone would be to present first the structure of the $\mathbb {F} _{4}$, and then to explain how it can be proved, and this is exactly the contrary that is done. I'll add a sentence at the beginning of the section for fixing this. D.Lazard (talk) 14:42, 18 September 2021 (UTC)

@Nomen4Omen: First: there are 4 polynomials of degree up to 1 in GF(2). Second: "up to one/less than two" would be more accurate. Third: both are valid ways of looking at it. What is most important is a worked out example of one multiplication, which I provided. We could also provide an example with the alpha representation. I don't know about which one is better for further calculations in general, seeing both is ideal. youtu.be/z9bTzjy4SCg?t=204 is how a person who first approaches this subject is more likely learn in my opinion. The goal is not to teach someone like you who already knows the subject, but to teach someone who does not. Cirosantilli2 (talk) 15:03, 18 September 2021 (UTC)

Cirosantilli2, The definition of polynomials requires the concept of a field. Thus, if the section is to be accessible to someone who first approaches this subject, you must not talk of polynomials in the first paragraph. D.Lazard (talk) 15:52, 18 September 2021 (UTC)

Still, there is something wrong with the F4 example. Construction principles just above explain that elements of the new field are polynomials (modulo the chosen irreducible polynomial).

Then, to build the concrete example of F4, an irreducible polynomial is chosen, and the rest of the example uses F2, completed with its newly created roots ad F4. That does not match at all the building principles : elements of F4 should be polynomials (actually polynomial classes), such as 0, 1, X an X + 1. Not roots of a given polynomial. Tanguy Ortolo (talk) 12:05, 7 February 2023 (UTC)

@Tanguy Ortolo:

Wrt. polynomial classes you are completely right. The following are the 4 polynomial classes in $\mathbb {F} _{4}$:

${\begin{array}{lllll}0&=&{\bar {0}}&=0&+(X^{2}+X+1)*\mathbb {F} _{2}[X]\\1&=&{\bar {1}}&=1&+(X^{2}+X+1)*\mathbb {F} _{2}[X]\\\alpha &=&{\overline {X}}&=X&+(X^{2}+X+1)*\mathbb {F} _{2}[X]\\\alpha +1&=&{\overline {X+1}}&=X+1&+(X^{2}+X+1)*\mathbb {F} _{2}[X]\end{array}}$

–Nomen4Omen (talk) 12:58, 7 February 2023 (UTC)

Formally, you are both right, but computing with sets (here equivalence classes) is counter-intuitive and error prone. It is much more easy to give a name,such as $\alpha ,$ to the class of X. So, the other elements of the field become polynomials in $\alpha ,$ and one has no more to consider the field elements as sets. I have added a paragraph to the article for explaining this. D.Lazard (talk) 13:23, 7 February 2023 (UTC)

GF(16)

In the example of GF(16) it seems instructive to me to mention the element ("symbol") $\alpha$ is a primitive root of the irreducible polynomial $X^{4}+X+1$. Madyno (talk) 15:08, 19 October 2021 (UTC)

In between the time I reverted your edit to the article and your post here, that information was added explicitly (just in a slightly different way than you had added it). --JBL (talk) 17:26, 19 October 2021 (UTC)

The article should just explicitly state $\alpha (X)=X$. Stating that $\alpha ^{4}=\alpha +1$, restricts $\alpha$ to 4 of the 8 multiplicative generators, since a quartic equation only has 4 roots. It's a poor way to define $\alpha$. This is mostly an issue for isomorphic mapping where the mapping can require using any of the 8 multiplicative generators in order to implement the mapping, including any of the 4 multiplicative generators where $\alpha ^{4}\neq \alpha +1$. Similarly in GF(8), $\alpha ^{3}=\alpha +1$, restricts $\alpha$ to 3 of the 6 multiplicative generators. Rcgldr (talk) 17:42, 19 October 2021 (UTC)

The elements are not necessarily polynomials, common choices are: (a) linear combinations of the powers $1,\,\alpha ,\,\alpha ^{2},\,\alpha ^{3}$ of a special element $\alpha$, a primitive root of unity. (b) Vectors $(a,b,c,d)$ over GF(2) with multiplication rules. Polynomials just form one of the possible representation of GF(16). In the polynomial representation any element may be written in the form $a+bx+cx^{2}+dx^{3},\ a,b,c,d\in \mathbb {GF} (2)$. The 16 elements of this form are all different, hence they form the whole field. The multiplication rules have to deal with higher powers of $x$. The theory states that a root of an irreducible polynomial over $\mathbb {GF} (2)$ acts as a generator. The polynomial $x^{4}+x+1$ is such a polynomial, but note: it's not (yet) an element of GF(16). If the generating root is called $\alpha$, it holds: $\alpha ^{4}=\alpha +1$, and there is the reducing equation. Because $\alpha \in \mathbb {GF} (16)$, it is of the form $\alpha =a+bx+cx^{2}+dx^{3}$. It follows that $\alpha$ is the identity polynomial $\alpha =x$, or better(?) $\alpha (x)=x$. Madyno (talk) 18:23, 19 October 2021 (UTC)

I have no idea what $\alpha (X)=X$ is supposed to mean. To concretely define GF(16), you need to make a concrete choice of irreducible polynomial; it doesn't matter which one you choose, but you do have to make a choice. The different choices of the irreducible polynomial lead to isomorphic structures, but the isomorphism cannot exchange one polynomial for the other. --JBL (talk) 17:47, 19 October 2021 (UTC)

This was a change suggested by Madyno for BCH codes. In most textbooks and articles for error correcting codes, isomorphic mapping, ... , the field reducing polynomial is defined, such as $x^{4}+x+1$ and $\alpha$ or $\alpha (x)$ is defined to be any of the 8 primitive elements | multiplicative generators: $\{x,x+1,x^{2},x^{2}+1,x^{3}+1,x^{3}+x+1,x^{3}+x^{2}+1,x^{3}+x^{2}+x\}$. A common example of this is for isomorphic mapping from $GF(2^{8})$ to $GF(((2^{2})^{2})^{2})$ used to reduce the number of gates in hardware for multiplicative inverse for the AES inversion step, where a brute force search is done for any of the 128 primitive elements | multiplicative generators of $GF(2^{8})$ where the isomorphic mapping works (map(a+b) = map(a)+map(b), map(ab) = map(a)map(b)), and minimizes gate count. The minimal polynomial primitive element $\alpha =x+1$ doesn't work and the optimal choice is usually $\alpha =x^{4}+x^{3}+x^{2}+x+1$. Rcgldr (talk) 18:07, 19 October 2021 (UTC)

Link to an example of a document that includes the isomorphic mapping for the AES inversion step on pages 4 and 5 of aessbox.pdf. Missing is an explanation for how the mapping matrix was generated, so I created a short explanation: mapping example.pdf Rcgldr (talk) 18:13, 19 October 2021 (UTC)

I have added a description of the primitive elements of GF(16).

It is well known that the terminology of coding theory is not the usual mathematical terminology. I suppose that the term "field reducing polynomial" is an example of such a term that is not used outside coding theory. I guess that "isomorphism mapping" means "field isomorphism". Apparently, the problem that you consider is to present GF(128) as a tower of field extensions of degree 2, in order to optimize the computation of multiplicative inverses. This is too specific for this article. As GF(256} is an important field, it could be worth write an article GF(256). If you do that, please notify me. D.Lazard (talk) 18:40, 19 October 2021 (UTC)

Does any of this discussion (after my first comment above) relate to the original post? Do we agree that that point is addressed? --JBL (talk) 19:11, 19 October 2021 (UTC)

Instead of using the term reducing polynomial you could use the mathematical syntax: $GF(2)[x]/\langle x^{4}+x+1\rangle$, but the current article does not use that syntax. The point here is that there are 8 multiplicative generators for $GF(2^{8})$ and stating that $\alpha ^{4}=\alpha +1$, restricts $\alpha$ to 4 of the 8 multiplicative generators. To get the other 4 (the inverses of the first 4), you need $\alpha ^{4}=\alpha ^{3}+1$, so the article could be $\alpha$ is a symbol such that $\alpha ^{4}=\alpha +1$ or $\alpha ^{4}=\alpha ^{3}+1$, or $\alpha ^{8}=\alpha ^{7}+\alpha ^{5}+\alpha ^{4}+\alpha ^{3}+\alpha +1$, which seems confusing, and I'm not sure how it would work for larger fields or when $p\neq 2$. Rcgldr (talk) 19:54, 19 October 2021 (UTC)

Are you proposing some change to the article? If so, I can't make heads or tails of what it is. (As I said above: To concretely define GF(16), you need to make a concrete choice of irreducible polynomial; it doesn't matter which one you choose, but you do have to make a choice. The same is true for any finite field: if you want to explicitly do computations, you choose an arbitrary irreducible polynomial; different choices of polynomials give you different (but isomorphic) arithmetics.) --JBL (talk) 21:18, 19 October 2021 (UTC)

My background is coding theory, so I'm used to seeing $\alpha$ defined as one element of a list of multiplicative generators as opposed to defining it as the roots (or inverses) of an equation. In most cases (other than isomorphic mapping), the minimal multiplicative element is used, for example for $GF(2)[x]/\langle x^{4}+x+1\rangle$ or $GF(2)[x]/\langle x^{4}+x^{3}+1\rangle$, $\alpha =x$, and for $GF(2)[x]/\langle x^{4}+x^{3}+x^{2}+x+1\rangle$, $\alpha =x+1$. I don't know if there a mathematical theory equivalent to this. I'm also wondering how many people would know that you can get the inverses of the roots of polynomial (in a Galios Field) by reversing the coefficients of the polynomial (reciprocal of the polynomial), and that the inverses of the multiplicative generators are also multiplicative generators. Who is the target audience for this Wikipedia article? Rcgldr (talk) 22:33, 19 October 2021 (UTC)

Who is the target audience for this Wikipedia article? Ideally, anyone who might use finite fields; that includes undergraduate students (certainly students taking abstract algebra, but perhaps even students taking linear algebra or number theory) but also more advanced audiences: mathematicians in various areas and people in neighboring fields like cryptography and coding theory.
I would expect the fact that you mention (that taking reciprocals of the roots of a polynomial (over any field) reverses the coefficients) to be known to any mathematician who has a reason to think about locations of roots of polynomials, but not necessarily to the entire audience for this article; the fact that the inverse of a multiplicative generator is also a multiplicative generator is a basic fact about either cyclic groups or the integers modulo n, depending on your point of view, and I would consider it more basic than the fact that the nonzero elements of a finite field form a cyclic group, for example.
But also I really have not understood what the purpose of your comments here is: what change are you proposing / what problem are you trying to solve? Could I convince you to spell it out very explicitly for me? --JBL (talk) 23:13, 19 October 2021 (UTC)

Your edit to include the inverses of generators for $GF(16)$ covers what I was getting at. Perhaps the same change could be made for GF(8) and GF(27). For coding theory, generally a single generator is chosen such as $\alpha =x$ or $\alpha (x)=x$ , rather than using two equations to define generators and their inverses which are also generators. As for "isomorphic mapping" versus "field isomorphism", which isn't mentioned in the article, "isomorphic mapping" refers to the algorithm used to map one field to another, usually by matrix multiplication using two matrices to map from one field to another and back. "Field isomorphism" means that all fields of the same size can be mapped to each other, without explaining the algorithms involved. Rcgldr (talk) 23:54, 19 October 2021 (UTC)

Suggestion

Just like the complex numbers may be derived from the reals by extending them with the special element $i$ satisfying $i^{2}+1=0$, the finite field GF(16) may be constucted by extending the field GF(2) by a special element α, which is a root of an irreducible polynomial of order 4 over GF(2). The polynomial

$X^{4}+X+1$

is irreducible over GF(2), that is, it is irreducible modulo 2. Hence the element α satisfies:

$\alpha ^{4}+\alpha +1=0$,

leading to the reducing equation

$\alpha ^{4}=\alpha +1$.

Any occurrence of $\alpha ^{4}$ in a computation will be replaced by $\alpha +1$. As α is a generator of the field it is also a primitive root of unity. In fact $\alpha ^{15}=1$. It follows that the elements of GF(16) may be represented by expressions

$a+b\alpha +c\alpha ^{2}+d\alpha ^{3},$

where a, b, c, d are either 0 or 1 (elements of GF(2)). As the characteristic of GF(2) is 2, each element is its additive inverse in GF(16). The addition and multiplication on GF(16) may be defined as follows; in following formulas, the operations between elements of GF(2), represented by Latin letters are the operations in GF(2).

${\begin{aligned}(a+b\alpha +c\alpha ^{2}+d\alpha ^{3})+(e+f\alpha +g\alpha ^{2}+h\alpha ^{3})&=(a+e)+(b+f)\alpha +(c+g)\alpha ^{2}+(d+h)\alpha ^{3}\\(a+b\alpha +c\alpha ^{2}+d\alpha ^{3})(e+f\alpha +g\alpha ^{2}+h\alpha ^{3})&=(ae+bh+cg+df)+(af+be+bh+cg+df+ch+dg)\alpha \;+\\&\quad \;(ag+bf+ce+ch+dg+dh)\alpha ^{2}+(ah+bg+cf+de+dh)\alpha ^{3}\end{aligned}}$

The field GF(16) has eight primitive elements (the elements that have all nonzero elements of GF(16) as integer powers). These elements are the four roots of $X^{4}+X+1$ and their multiplicative inverses. In particular, α is a primitive element, and the primitive elements are $\alpha ^{m}$ with m less than and coprime with 15 (that is, 1, 2, 4, 7, 8, 11, 13, 14).

Another way of introducing the complex numbers is as pairs of real numbers, with a special rule for multiplication. In an analogous way the field GF(16) may be seen as a 4 dimensional linear space over GF(2) with a multiplication according to some special rules. The elements of GF(16) then are of the form $(d,c,b,a)$ with $a,b,c,d\in \mathrm {GF} (2)$. These rules are:

• $(d,c,b,a)*(0,0,0,1)=(d,c,b,a)$
• $(0,c,b,a)*(0,0,1,0)=(c,b,a,0)$
• $(1,0,0,0)*(0,0,1,0)=(0,0,1,1)$

Notice the analogy between $(0,0,0,1)$, $(0,0,1,0)$ and 1 and α in the first representation. The last rule is analogous to $\alpha ^{3}\cdot \alpha =\alpha +1$. Madyno (talk) 22:19, 25 October 2021 (UTC)

I oppose to this formulation. The main reason is that it presents as specific to GF(16) general properties that are presented in other sections, mainly § Non-prime fields, which ends with "In the next sections, we will show how the general construction method outlined above works for small finite fields". The suggested version ignores totally this sentence. D.Lazard (talk) 08:40, 26 October 2021 (UTC)

@Madyno:This approach doesn't work well for fields larger than $GF(2^{4})$. Consider the field $GF(2)[x]/\langle x^{8}+x^{4}+x^{3}+x^{2}+1\rangle$, (or any $GF(2^{8})$). There are 128 generators, but $\alpha ^{8}+\alpha ^{4}+\alpha ^{3}+\alpha ^{2}+1=0$ only provides a solution for 8 of the generators. There are 16 primitive polynomials in $GF(2^{8})$, 8 polynomials and their 8 reciprocals (coefficients reversed, resulting in inverses). I didn't test this, but I suspect the roots of the 16 primitive polynomials in any $GF(2^{8})$ will result in the 128 generators for that $GF(2^{8})$. This would be inefficient and scales worse for larger still fields, such as $GF(2^{32})$. If a list of all the generators is needed, such as trying to optimize multiplicative inverse in hardware by isomorphic mapping with a brute for test of all generators to find an optimal generator, the normal approach is to test all products of all combinations of the prime factors of $2^{8}-1=255$, where the prime factors are $3,5,17$ and 128 generators will pass 3 checks: $\alpha ^{15}\neq 1$, $\alpha ^{51}\neq 1$, $\alpha ^{85}\neq 1$. Rcgldr (talk) 15:01, 26 October 2021 (UTC)

Let me follow the indicated lines. $GF(16)~GF(2)[x]/(x^{4}+x+1)$, i.e. an element is formally a residue class with a representant $a$ of the form:
$\quad a(x)=a_{3}x^{3}+a_{2}x^{2}+a_{1}x+a_{0}$
For the sake of simplicity $a$ itself is written as $a_{3}x^{3}+a_{2}x^{2}+a_{1}x+a_{0}$. The element $x^{4}+x+1$ is in the same residue class as zero. Is it now meaningful to say $x$ is a zero of $x^{4}+x+1$? Madyno (talk) 11:31, 29 October 2021 (UTC)

The polynomial $x^{4}+x+1$ belongs to the ring $GF(2)[x]$; the symbol $x$ in this ring does not satisfy any polynomial equations. The thing that satisfies the polynomial equation is the image of $x$ in the quotient $GF(2)[x]/\langle x^{4}+x+1\rangle$; it is not the same as the formal symbol being used to write down the polynomials in the first place.

Independent of the preceding paragraph: why would you want to write down this extremely confusing way of expressing things? How would it help the reader understand a construction of GF(16), and thereby understand the general phenomenon of finite fields? I contend that it does not conceivably help. --JBL (talk) 11:54, 29 October 2021 (UTC)

@Madyno: - Clarifying my prior comment. This approach doesn't work when the reducing polynomial is irreducible, but not primitive. For example in $GF(2)[x]/\langle x^{4}+x^{3}+x^{2}+x+1\rangle$, $\alpha ^{4}+\alpha ^{3}+\alpha ^{2}+\alpha +1\neq 0$. However, a primitive polynomial equation of degree $n$ in $\alpha$ will work in any field, even if it's reducing polynomial is irreducible, but not primitive. For example $\alpha ^{4}+\alpha +1=0$ and its reciprocal $\alpha ^{4}+\alpha ^{3}+1=0$ are true in $GF(2)[x]/\langle x^{4}+x+1\rangle$ or $GF(2)[x]/\langle x^{4}+x^{3}+1\rangle$, or $GF(2)[x]/\langle x^{4}+x^{3}+x^{2}+x+1\rangle$ Rcgldr (talk) 21:43, 1 November 2021 (UTC)

Yes, and in the article the polynomial $X^{4}+X+1$ somehow just pops up out of the blue. One easily could have written $X^{4}+X^{3}+X^{2}+X+1$ as an irreducible polynomial. And then the approach would fail. Madyno (talk) 14:55, 2 November 2021 (UTC)

Please, read the article before posting here. The polynomial $X^{4}+X+1$ does not pop up out of the blue, as its choice is expained in § Non-prime fields. D.Lazard (talk) 15:22, 2 November 2021 (UTC)

§ Non-prime fields mentions irreducible polynomials, which for $GF(2^{4})$, would include $x^{4}+x+1$, $x^{4}+x^{3}+1$, or $x^{4}+x^{3}+x^{2}+x+1$. I'm missing where the choice of $x^{4}+x+1$ is explained. The approach used in the article fails for irreducible non-primitive polynomials as noted by Madyno Rcgldr (talk) 16:15, 2 November 2021 (UTC)

The approach described in the article works fine with $x^{4}+x^{3}+x^{2}+x+1$ in place of $X^{4}+X+1$. --JBL (talk) 17:16, 2 November 2021 (UTC)

I've tested this using a finite field calculator, for $GF(2)[x]/\langle x^{4}+x^{3}+x^{2}+x+1\rangle$, one of the 8 primitive elements is $x+1$ or in hex $3$. In this field, $3^{4}+3^{3}+3^{2}+3+1=6$ . Note that $x$ or in hex $2$ is not a primitive element of this field. Rcgldr (talk) 18:36, 2 November 2021 (UTC)

Yes but the article does not assert that it should be. It is very important to you that the article should not assert, in the section on GF(16), that if you use an arbitrary irreducible polynomial, one of its roots will be a primitive generator for the multiplicative subgroup of the field. Since no assertion even vaguely like that is in the article, there is literally no problem. The section about the field with 16 elements is not an appropriate place to clarify general phenomena about the difference between polynomials whose roots generate the field algebraically (all irreducible polynomials) and those whose roots generate the cyclic group under multiplication; those generalities are treated in the following section, along with a concrete example of GF(64). --JBL (talk) 19:52, 2 November 2021 (UTC)

True, but some readers might infer that the approach used would work for all polynomials. The article could simply mention that the approach used only works for primitive polynomials. Rcgldr (talk) 22:37, 2 November 2021 (UTC)

The article could simply mention that the approach used only works for primitive polynomials. "The approach used" in the section on GF(16) is a completely general approach for constructing finite fields; it works for any irreducible polynomial. It then happens that the generator used in the concrete construction GF(16) is actually a cyclic generator for the multiplicative subgroup (but this is not part of "the approach used" to construct the field, which is what is illustrated in the section). The phenomenon of primitivity (and in particular the fact that not all field generators are multiplicative generators) is discussed in general and at length in the following section, Finite field#Multiplicative structure. --JBL (talk) 23:18, 2 November 2021 (UTC)

Madyno comments above One easily could have written $X^{4}+X^{3}+X^{2}+X+1$ as an irreducible polynomial. And then the approach would fail. I leave it to you and the others here to decide if any change is needed. Rcgldr (talk) 23:32, 2 November 2021 (UTC)

Are you unable to understand "To simplify the Euclidean division, for P one commonly chooses polynomials of the form $X^{n}+aX+b$, which make the needed Euclidean divisions very efficient"?. D.Lazard (talk) 17:26, 2 November 2021 (UTC)

In your style: Are you unable to understand the meaning of the word 'commonly'? Madyno (talk) 13:05, 5 November 2021 (UTC)

Here is this exchange so far: you wrote "it pops out of the blue". D.Lazard's response is that it doesn't pop out of the blue, it is specifically advertised by the sentence he quotes. Your response is ... totally inscrutable; what's wrong with the word "commonly"? How does the presence of the word "commonly" invalidate D.Lazard's point? How does the presence of the word "commonly" make that sentence not a specific advertisement of the particular choice made later? --JBL (talk) 13:11, 5 November 2021 (UTC)

From the article: simplify Euclidean division ... polynomials of the form $X^{n}+aX+b$ commonly used. For $GF(16)$, wouldn't lookup tables more commonly used than Euclidean division? My impression is that "pops out of the blue" was specific to $GF(16)$. My issue with this section is that readers may think that since for $X^{4}+X+1$ and $\alpha ^{4}+\alpha +1=0$, that that the two polynomials are directly related, that the same idea could be used for $X^{4}+X^{3}+X^{2}+X+1$, but $\alpha ^{4}+\alpha ^{3}+\alpha ^{2}+\alpha +1\neq 0$. There should be some mention that the generators of a field are the roots of primitive polynomials, which may or may not be of similar form to the reducing polynomial. Rcgldr (talk) 20:50, 5 November 2021 (UTC)

Yes, I understand this. My concern is not the choice of polynomial, but that the approach used in § GF(16) could be mistakenly inferred to apply to any choice of polynomial. Note that AES inversion step uses a non-primitive polynomial (I'm not sure why, but it was a deliberate choice). Rcgldr (talk) 18:41, 2 November 2021 (UTC)

The second sentence of WP:TALK is Article talk pages should not be used by editors as platforms for their personal views on a subject.. So, please stop such posts, which are WP:DISRUPTIVE, not only because they do not respect the guideline WP:TALK, but also because it is a tentative to continue a discussion on which a clear consensus has been reach. This post is also disruptive by using a never defined notation that makes impossible to check whether it is mathematically correct (I suspect that it is not), D.Lazard (talk) 08:44, 2 November 2021 (UTC)

I don't understand what you mean by "never defined notation" or what specific statement should be checked to see if it is "mathematically correct". This isn't my personal view; my first recollection of this issue was in a class taught by Professor E J Weldon Jr in the late 1980's. There should be an explanation that works for irreducible non-primitive polynomials (such as the one used for AES inversion step) as well. Rcgldr (talk) 17:11, 2 November 2021 (UTC)

By "never defined", I mean that this use of angle brackets is not defined in Wikipedia and the standard texbooks on the subject. The angle brackets are commonly used for the generated ideal, but in this context, that is just after the name of a ring, they require to be preceded by a slash (/) for indicating a quotient ring (see JBL's post). It is possible that this is that you have in mind, but the surrounding is too confusing for deciding this possibility. Also, if there is an error in the article, such that ommitting a needed hypothesis ("primitive reducing polynomial"), you must be accurate and say which sentence is erroneous. Otherwise, your posts are simply WP:disruptive editing. D.Lazard (talk) 17:26, 2 November 2021 (UTC)

The missing slash was a typo error on my part (fixed now, I thought I had fixed this before). I see angle brackets or parenthesis used at Stack Exchange for finite fields, and I'm not sure which is preferred. The "error" in the article is what some readers could infer from seeing the GF(16) reducing polynomial defined as $X^{4}+X+1$ followed by: $\alpha$ is such a symbol such that $\alpha ^{4}+\alpha +1=0$ and that $\alpha$ is a primitive element. This approach doesn't work if the reducing polynomial is non-primitive, for example, if the GF(16) irreducible reducing polynomial is $X^{4}+X^{3}+X^{2}+X+1$ then $\alpha ^{4}+\alpha ^{3}+\alpha ^{2}+\alpha +1\neq 0$ assuming $\alpha$ is a primitive element. The article should define how multiplication could be implemented for non-primitive as well as primitive polynomials. Rcgldr (talk) 18:09, 2 November 2021 (UTC)

No, it shouldn't do that in the section on the field with 16 elements -- that section should be devoted to describing the field with 16 elements, which it currently does (completely correctly). The problem of primitive elements is addressed, in appropriate generality, elsewhere in the article. --JBL (talk) 18:15, 2 November 2021 (UTC)

The multiplication is implemented by reducing the multiplication of polynomials by the reducing polynomial (as it is defined for every quotient ring). This works for the irreducible polynomial with five terms as well as for those with three terms. The only difference is that reducing by a 5 terms polynomial is more difficult and more time consuming. The use of primitive elements for multiplication is normally done with Zech's logarithms. This is not useful for small fields such as GF(16} and not practicable for very large fields. It is useful only for medium-sized fields not for GF(16}. D.Lazard (talk) 18:41, 2 November 2021 (UTC)

Off topic, since it's not GF(16) specific, but if not using tables, software implementations based on CLMUL_instruction_set such as X86 PCLMULQDQ (for XMM registers) is not sensitive to the number of terms in the polynomial $P$. A one time pre-computed value $2^{64}/P$ (borrowless divide) is used for this purpose. For PCLMULQDQ, this works directly for fields up to $GF(2^{32})$, and can be extended to work with larger fields. For hardware implementations, gate count can be reduced using isomorphic mapping such as $GF(2^{8})$ to $GF(((2^{2})^{2})^{2})$ (this is used in AES s-box chips). Rcgldr (talk) 19:05, 2 November 2021 (UTC)

Multiplication in GF(16)

The given formula for multiplication does not give much insight. Better would be to give separately the multiplication with the powers of $\alpha$:

$(p+q\alpha +r\alpha ^{2}+s\alpha ^{3})\alpha =p\alpha +q\alpha ^{2}+r\alpha ^{3}+s\alpha ^{4}=$

$=p\alpha +q\alpha ^{2}+r\alpha ^{3}+s(1+\alpha )=s+(p+1)\alpha +q\alpha ^{2}+r\alpha ^{3}$

etc.

Madyno (talk) 09:47, 3 November 2021 (UTC)

Shouldn't that be:

$=p\alpha +q\alpha ^{2}+r\alpha ^{3}+s(1+\alpha )=s+(p+s)\alpha +q\alpha ^{2}+r\alpha ^{3}$

The current given formula seems correct (I only checked some of terms) for reducing polynomial $X^{4}+X+1$. I didn't investigate multiplication with the non primitive reducing polynomial $X^{4}+X^{3}+X^{2}+X+1$, but if the multiplication formula is based on $\alpha ^{4}=\alpha +1$ or $\alpha ^{4}=\alpha ^{3}+1$ it will work for $X^{4}+X^{3}+X^{2}+X+1$, with the issue that $\alpha \neq x$. If using $\alpha ^{4}=\alpha ^{3}+1$, then one of the roots is $\alpha =x+1$, still messy. The terms for multiplication modulo $X^{4}+X^{3}+X^{2}+X+1$ could be worked out directly in terms of $x$ instead of $\alpha$. It seems unlikely to implement the given formula in software where a table, carryless multiply, or loop could be used instead. Hardware could use a loop with a LFSR, or if the speed was needed, using the current formula via a bunch of AND and XOR gates, but it would be simpler to specify the logic similar to an unfolded loop, and rely on an optimizer to convert the logic into the equivalent of the current formula. I'm wondering how much of implementation belongs here as opposed to Finite_field_arithmetic. Rcgldr (talk) 18:34, 3 November 2021 (UTC)

You're right. My intention is not to indicate an error, but to split up the calculation to make it easier to follow. Madyno (talk) 13:33, 4 November 2021 (UTC)

Readability

@D.Lazard: For myself this line is highly unreadable

such that $\alpha ^{2}=1+\alpha ,$ $1\cdot \alpha =\alpha \cdot 1=\alpha ,$ $x+x=0,$ and $x\cdot 0=0\cdot x=0,$ for every $x\in \operatorname {GF} (4),$

I recommend that do something to make it more readable. — Preceding unsigned comment added by Hooman Mallahzadeh (talk • contribs)

It's four short equations separated by commas, what's the problem? --JBL (talk) 12:48, 16 December 2021 (UTC)

@JayBeeEll: Comma and dot symbols are very similar. We should do something that the reader identifies the equations with low mental attempt. I recommend use a "color" or as before a "newline" to identify each separate equation more clearly.

Template "Ring theory sidebar"

Hi again @D.Lazard:

No, links in Template:Ring theory sidebar is not unrelated, both in "Basic concepts" and in "Commutative algebra" there is a link named "finite field", and by using the second link the reader can find that "finite field" is a concept in "Commutative algebra" and "Commutative rings" and I persist to insert this template, but you are right about its huge space consumption. We can use "none" its argument so that the output of {{Ring theory sidebar|none}} becomes

. Do you agree? Hooman Mallahzadeh (talk) 17:31, 17 December 2021 (UTC)

WP:NAVBOX says Navigation templates are a grouping of links used in multiple related articles to facilitate navigation between those articles in Wikipedia. Here, almost all of the links of the navbox are unrelated or weakly related with finite fields. The only significant relation is that finite fields are rings. Moreover, the tools of ring theory are generally not used for fields because they become trivial in this case. On the other hand, the algebraic tools that are used for fields, such as automorphism groups, and linear algebra oover a field are not covered by ring theory. So this navbox is not useful for most readers of this article. It may even be confusing, since many readers do not even know of rings that are not fields.

So, this template does not belong to this article, even if it contain a link to this article. D.Lazard (talk) 18:16, 17 December 2021 (UTC)

@D.Lazard:It depends on how we define a "relation". I think some relations are "is a" relations i.e.

Finite field "is a" field.

Finite field "is a" Integral domain.

Finite field "is a" Commutative ring.

Finite field "is a" Commutative algebra concept.

Finite field "is a" ring

and etc.

Some relations are "is not a" relations i.e.

Finite field is not a "Algebraic number theory"

Finite field is not a "Noncommutative algebra"

and etc.

Some relations are "is similar to" relations i.e.

Finite field "is similar to" Euclidean domain because they are both Integral domain.

and etc.

This way, all of the template links have some relationship to the "Finite filed" concept i.e., a relationship may be an "is a" or an "is not a" or an "is similar to". Hooman Mallahzadeh (talk) 19:58, 17 December 2021 (UTC)

Mention of Parker and Non-Parker finite fields?

I don't know all too much about fields, but upon browsing YouTube, I was reminded of a Numberphile video about finite fields (2021) (extra footage: here) which mentioned a concept of 'Parker' and 'Non-Parker' finite fields. The video cites the paper mentioned: Gaussian Integers, Rings, Finite Fields, and the Magic Square of Squares, and I was just wondering if this was significant enough to be mentioned in this article or not?

The video has almost 300,000 views, so I think it might be worth a mention maybe? However, I do recognise that a 'Parker Square' is a bit more of a meme than a recognised mathematical idea, but since a research paper has been released, maybe the article should mention the concept of 'Parker Finite Fields' and 'Non-Parker Finite Fields'?

Just a suggestion. :) – Pigeon <3 (talk) 13:54, 15 February 2022 (UTC)

This is not really about finite fields, it is about Magic squares. So there is no reason for mentioning it here. Also this is published only in Youtube and ArXiV, which are not considered as WP:Reliable sources in Wikipedia. There is no WP:secondary sources for establishing the notability of the concept and related results. So, this is considered here as WP:original research, and Wikipedia policy is to not publishing original research. So, the answer is no for both questions. D.Lazard (talk) 14:49, 15 February 2022 (UTC)

I agree with D.Lazard. --JBL (talk) 15:01, 15 February 2022 (UTC)

Thought as much, but thanks for letting me know! It was only a thought anyway :) – Pigeon <3 (talk) 19:59, 15 February 2022 (UTC)

great use of plain language

This is a great example of trying to convey a point with a minimum of jargon or presupposed knowledge, and then providing the technical term. This makes it easier for those newer to a topic to grasp the concepts and learn the jargon without having to first look up many unfamiliar terms. Kudos to those who developed this entry! D1717 (talk) 11:15, 22 June 2023 (UTC)

Algebraic closure

Section § Algebraic closure was illogically presented by starting from the algebraic closure for deducing properties already described in the preceding sections, instead of starting from these properties for deducing the properties of the algebraic closure. I have fixed this.

By the way, I removed the paragraph about the absolute Galois group for the following reasons:

• It is completely unsourced, even when taken into account all linked articles.
• It is very confusing, as asserting implicitly that the Frobenius homorphism is an automorphism of the algebraic closure (this is probably true, but nowere explicited in Wikipedia)
• It is definitively out of scope of this article, since it involves many theories that the readers of this article (interested in fields) are not supposed to know (infinite Galois groups, profinite groups, Krull topology, topological groups, etc.)

The subject absolute Galois group of a finite field is interesting, but it is not adapted to the readers of this article. It must either be the object of a specific article, or be a detailed section in Absolute Galois group. The involved formalism makes it definitively unsuited for this article. D.Lazard (talk) 18:59, 2 December 2023 (UTC)