F J MacWilliams and I deal with this in our book on Error-Correcting Codes See pages 110ff and 124 for example. There are papers by Neal Zierler in the journal "information and Control", for example Zierler, Neal, and John Brillhart. "On primitive trinomials (mod 2)." *Information and Control* 13.6 (1968): 541-554. Best regards Neil Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com On Mon, Jan 18, 2021 at 7:23 AM Joerg Arndt <arndt@jjj.de> wrote:

Possibly making a fool of myself... Have you checked 'the Bible' (Lidl, Niederreiter)? I seem to recall that there is a nontrivial amount of coverage about binomial polynomials, specifically regarding irreducibility.

Best regards, jj

...

Let $n = 2^{e_0} q_1^{e_1} \cdots q_i^{e_i}$ be the prime factorization of $n$. Let $p$ be an odd prime. Is it true that $\exists k$ such that $x^n+k$ is irreducible over GF($p$) $\iff$ $(2^{min(e_0,2)} q_1 \cdots q_i) | (p-1)$ ?

Are there similar criteria for "larger" polynomials such as $x^n + k_1 x

* Mike Speciner <ms@alum.mit.edu> [Jan 14. 2021 17:11]: +

...

k_0$ ?

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

Here's the first 64, with the x^n term elided; constant term last. Not an obvious pattern, and, interpreted as a binary number, not in OEIS (either with or without the x^n term)... 'GF2_2_0' 'GF2_2_11' 'GF2_3_11' 'GF2_4_11' 'GF2_5_101' 'GF2_6_11' 'GF2_7_11' 'GF2_8_11011' 'GF2_9_11' 'GF2_10_1001' 'GF2_11_101' 'GF2_12_1001' 'GF2_13_11011' 'GF2_14_100001' 'GF2_15_11' 'GF2_16_101011' 'GF2_17_1001' 'GF2_18_1001' 'GF2_19_100111' 'GF2_20_1001' 'GF2_21_101' 'GF2_22_11' 'GF2_23_100001' 'GF2_24_11011' 'GF2_25_1001' 'GF2_26_11011' 'GF2_27_100111' 'GF2_28_11' 'GF2_29_101' 'GF2_30_11' 'GF2_31_1001' 'GF2_32_10001101' 'GF2_33_1001011' 'GF2_34_11011' 'GF2_35_101' 'GF2_36_110101' 'GF2_37_111111' 'GF2_38_1100011' 'GF2_39_10001' 'GF2_40_111001' 'GF2_41_1001' 'GF2_42_100111' 'GF2_43_1011001' 'GF2_44_100001' 'GF2_45_11011' 'GF2_46_11' 'GF2_47_100001' 'GF2_48_101101' 'GF2_49_1110001' 'GF2_50_11101' 'GF2_51_1001011' 'GF2_52_1001' 'GF2_53_1000111' 'GF2_54_1111101' 'GF2_55_1000111' 'GF2_56_10010101' 'GF2_57_10001' 'GF2_58_1100011' 'GF2_59_1111011' 'GF2_60_11' 'GF2_61_100111' 'GF2_62_1101001' 'GF2_63_11' 'GF2_64_11011' On 18-Jan-21 12:01, James Propp wrote:

If I’m not mistaken, Conway’s notion of Nim-multiplication gives a way of singling out a “first” degree n irreducible polynomial over GF(2). For instance, x = *4 satisfies x^2 = *6, x^3 = *14, and x^4 = *5, so the first irreducible polynomial of degree 4 is x^4 + x + 1.

It would be interesting to peruse these polynomials for the first dozen powers of 2 to see if there’s a simple pattern.

When n isn’t a power of 2 you need to use Nim-values associated with infinite ordinals but that’s okay since they’re well-ordered.

Jim Propp

On Mon, Jan 18, 2021 at 7:23 AM Joerg Arndt <arndt@jjj.de> wrote:

...

Possibly making a fool of myself... Have you checked 'the Bible' (Lidl, Niederreiter)? I seem to recall that there is a nontrivial amount of coverage about binomial polynomials, specifically regarding irreducibility.

Best regards, jj

...

Let $n = 2^{e_0} q_1^{e_1} \cdots q_i^{e_i}$ be the prime factorization of $n$. Let $p$ be an odd prime. Is it true that $\exists k$ such that $x^n+k$ is irreducible over GF($p$) $\iff$ $(2^{min(e_0,2)} q_1 \cdots q_i) | (p-1)$ ?

Are there similar criteria for "larger" polynomials such as $x^n + k_1 x

* Mike Speciner <ms@alum.mit.edu> [Jan 14. 2021 17:11]: +

...

k_0$ ?

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

---

math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

Yes, those are the lexicographically smallest. Were you asking for the ones with fewest terms? Something else? It wasn't clear to me. Just done with a brute-force search. (I wrote some code a while back when I was playing with finite fields for a demonstration of secret sharing. Ended up with a python  library with classes for such things as finite fields, rationals/complex rationals/quaternion rationals, matrices, polynomials. (https://github.com/ms0/pymath) The question I asked at the start of this thread was really about short-circuiting that brute-force search a bit, at least for odd characteristic. I'm testing with the deterministic Rabin irreducibility test. Of course, I can easily generate a similar table for other primes. (Python isn't fast, but it's easy to code in; the p=2 case does everything with bitwise operations, so it's not as slow as it could be.) On 18-Jan-21 16:43, James Propp wrote:

Thanks, Mike!

Looks like you tackled all the Galois fields GF(2^n), not just GF(2^(2^k)). How did you do it?

Let me make sure I understand your notation. Does GF2_15_11 mean the polynomial 1 + x + x^15?

I am surprised that the bit strings you found are so short (corresponding to most of the high-degree coefficients being zero). It makes me wonder whether you answered a different question than the one I asked, and computed the lexicographically first irreducible polynomial of degree n. That’s an interesting question too, but I see no reason why they should have the same answer.

Jim Propp

On Mon, Jan 18, 2021 at 3:35 PM Mike Speciner <ms@alum.mit.edu <mailto:ms@alum.mit.edu>> wrote:

Here's the first 64, with the x^n term elided; constant term last. Not an obvious pattern, and, interpreted as a binary number, not in OEIS (either with or without the x^n term)...

'GF2_2_0' 'GF2_2_11' 'GF2_3_11' 'GF2_4_11' 'GF2_5_101' 'GF2_6_11' 'GF2_7_11' 'GF2_8_11011' 'GF2_9_11' 'GF2_10_1001' 'GF2_11_101' 'GF2_12_1001' 'GF2_13_11011' 'GF2_14_100001' 'GF2_15_11' 'GF2_16_101011' 'GF2_17_1001' 'GF2_18_1001' 'GF2_19_100111' 'GF2_20_1001' 'GF2_21_101' 'GF2_22_11' 'GF2_23_100001' 'GF2_24_11011' 'GF2_25_1001' 'GF2_26_11011' 'GF2_27_100111' 'GF2_28_11' 'GF2_29_101' 'GF2_30_11' 'GF2_31_1001' 'GF2_32_10001101' 'GF2_33_1001011' 'GF2_34_11011' 'GF2_35_101' 'GF2_36_110101' 'GF2_37_111111' 'GF2_38_1100011' 'GF2_39_10001' 'GF2_40_111001' 'GF2_41_1001' 'GF2_42_100111' 'GF2_43_1011001' 'GF2_44_100001' 'GF2_45_11011' 'GF2_46_11' 'GF2_47_100001' 'GF2_48_101101' 'GF2_49_1110001' 'GF2_50_11101' 'GF2_51_1001011' 'GF2_52_1001' 'GF2_53_1000111' 'GF2_54_1111101' 'GF2_55_1000111' 'GF2_56_10010101' 'GF2_57_10001' 'GF2_58_1100011' 'GF2_59_1111011' 'GF2_60_11' 'GF2_61_100111' 'GF2_62_1101001' 'GF2_63_11' 'GF2_64_11011'

On 18-Jan-21 12:01, James Propp wrote: > If I’m not mistaken, Conway’s notion of Nim-multiplication gives a way of > singling out a “first” degree n irreducible polynomial over GF(2). For > instance, x = *4 satisfies x^2 = *6, x^3 = *14, and x^4 = *5, so the first > irreducible polynomial of degree 4 is x^4 + x + 1. > > It would be interesting to peruse these polynomials for the first dozen > powers of 2 to see if there’s a simple pattern. > > When n isn’t a power of 2 you need to use Nim-values associated with > infinite ordinals but that’s okay since they’re well-ordered. > > Jim Propp > > On Mon, Jan 18, 2021 at 7:23 AM Joerg Arndt <arndt@jjj.de <mailto:arndt@jjj.de>> wrote: > >> Possibly making a fool of myself... >> Have you checked 'the Bible' (Lidl, Niederreiter)? >> I seem to recall that there is a nontrivial amount >> of coverage about binomial polynomials, specifically >> regarding irreducibility. >> >> Best regards,   jj >> >> >> * Mike Speciner <ms@alum.mit.edu <mailto:ms@alum.mit.edu>> [Jan 14. 2021 17:11]: >>> Let $n = 2^{e_0} q_1^{e_1} \cdots q_i^{e_i}$ be the prime factorization >> of >>> $n$. >>> Let $p$ be an odd prime. >>> Is it true that >>> $\exists k$ such that $x^n+k$ is irreducible over GF($p$) $\iff$ >>> $(2^{min(e_0,2)} q_1 \cdots q_i) | (p-1)$ ? >>> >>> Are there similar criteria for "larger" polynomials such as $x^n + k_1 x >> + >>> k_0$ ? >>> >>> >>> _______________________________________________ >>> math-fun mailing list >>> math-fun@mailman.xmission.com <mailto:math-fun@mailman.xmission.com> >>> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun <https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun> >> _______________________________________________ >> math-fun mailing list >> math-fun@mailman.xmission.com <mailto:math-fun@mailman.xmission.com> >> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun <https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun> >> > _______________________________________________ > math-fun mailing list > math-fun@mailman.xmission.com <mailto:math-fun@mailman.xmission.com> > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun <https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>

The the first nine powers of *16 (according to https://www.math.ucla.edu/~tom/NimProd.html) are *1, *16, *24, *152, *21, *72, *203, *118, and *31. In base 2 these are represented by the rows of the matrix {{0,0,0,0,0,0,0,1}, {0,0,0,1,0,0,0,0}, {0,0,0,1,1,0,0,0}, {1,0,0,1,1,0,0,0}, {0,0,0,1,0,1,0,1}, {0,1,0,0,1,0,0,0}, {1,1,0,0,1,0,1,1}, {0,1,1,1,0,1,1,0}, {0,0,0,1,1,1,1,1}} whose mod-2 annihilator is [1,1,0,1,1,1,1,0,1], so the minimal polynomial of *16 (if I haven't goofed) is x^8 + x^6 + x^5 + x^4 + x^3 + x + 1. Jim Propp On Mon, Jan 18, 2021 at 6:17 PM James Propp <jamespropp@gmail.com> wrote:

See https://en.m.wikipedia.org/wiki/Nimber . Conway’s definition of multiplication gives us a way to view the finite nimbers *0, *1, *2, *3, *4, ... as the nested union of GF(2), GF(4), GF(16), GF(256), etc.

The elements of GF(4) are *0, *1, *2, and *3, and the “first” element of GF(16) that isn’t in GF(4) is *4. For what irreducible polynomial p( ) over GF(2) do we have p(x) = 0 when x = *4? Putting x = *4 we compute x^2 = *6 (this is the discovery that made Conway wiggle his legs in the air in delight), x^3 = *14, and x^4 = *5, giving x^4 + x^1 + x^0 = *5 + *4 + *1 = *0. So the minimal polynomial of *8 in GF(16) is x^4+x+1.

To bring GF(8) etc. into the game, we need to extend the game to nimbers associated with countable ordinals. As I recall, *omega is a cube root of *2.

Jim Propp

On Mon, Jan 18, 2021 at 5:33 PM Mike Speciner <ms@alum.mit.edu> wrote:

...

Yes, those are the lexicographically smallest. Were you asking for the ones with fewest terms? Something else? It wasn't clear to me.

Just done with a brute-force search. (I wrote some code a while back when I was playing with finite fields for a demonstration of secret sharing. Ended up with a python library with classes for such things as finite fields, rationals/complex rationals/quaternion rationals, matrices, polynomials. (https://github.com/ms0/pymath)

The question I asked at the start of this thread was really about short-circuiting that brute-force search a bit, at least for odd characteristic. I'm testing with the deterministic Rabin irreducibility test. Of course, I can easily generate a similar table for other primes. (Python isn't fast, but it's easy to code in; the p=2 case does everything with bitwise operations, so it's not as slow as it could be.)

On 18-Jan-21 16:43, James Propp wrote:

Thanks, Mike!

Looks like you tackled all the Galois fields GF(2^n), not just GF(2^(2^k)). How did you do it?

Let me make sure I understand your notation. Does GF2_15_11 mean the polynomial 1 + x + x^15?

I am surprised that the bit strings you found are so short (corresponding to most of the high-degree coefficients being zero). It makes me wonder whether you answered a different question than the one I asked, and computed the lexicographically first irreducible polynomial of degree n. That’s an interesting question too, but I see no reason why they should have the same answer.

Jim Propp

On Mon, Jan 18, 2021 at 3:35 PM Mike Speciner <ms@alum.mit.edu> wrote:

...

Here's the first 64, with the x^n term elided; constant term last. Not an obvious pattern, and, interpreted as a binary number, not in OEIS (either with or without the x^n term)...

'GF2_2_0' 'GF2_2_11' 'GF2_3_11' 'GF2_4_11' 'GF2_5_101' 'GF2_6_11' 'GF2_7_11' 'GF2_8_11011' 'GF2_9_11' 'GF2_10_1001' 'GF2_11_101' 'GF2_12_1001' 'GF2_13_11011' 'GF2_14_100001' 'GF2_15_11' 'GF2_16_101011' 'GF2_17_1001' 'GF2_18_1001' 'GF2_19_100111' 'GF2_20_1001' 'GF2_21_101' 'GF2_22_11' 'GF2_23_100001' 'GF2_24_11011' 'GF2_25_1001' 'GF2_26_11011' 'GF2_27_100111' 'GF2_28_11' 'GF2_29_101' 'GF2_30_11' 'GF2_31_1001' 'GF2_32_10001101' 'GF2_33_1001011' 'GF2_34_11011' 'GF2_35_101' 'GF2_36_110101' 'GF2_37_111111' 'GF2_38_1100011' 'GF2_39_10001' 'GF2_40_111001' 'GF2_41_1001' 'GF2_42_100111' 'GF2_43_1011001' 'GF2_44_100001' 'GF2_45_11011' 'GF2_46_11' 'GF2_47_100001' 'GF2_48_101101' 'GF2_49_1110001' 'GF2_50_11101' 'GF2_51_1001011' 'GF2_52_1001' 'GF2_53_1000111' 'GF2_54_1111101' 'GF2_55_1000111' 'GF2_56_10010101' 'GF2_57_10001' 'GF2_58_1100011' 'GF2_59_1111011' 'GF2_60_11' 'GF2_61_100111' 'GF2_62_1101001' 'GF2_63_11' 'GF2_64_11011'

On 18-Jan-21 12:01, James Propp wrote:

...

If I’m not mistaken, Conway’s notion of Nim-multiplication gives a way of singling out a “first” degree n irreducible polynomial over GF(2). For instance, x = *4 satisfies x^2 = *6, x^3 = *14, and x^4 = *5, so the first irreducible polynomial of degree 4 is x^4 + x + 1.

It would be interesting to peruse these polynomials for the first dozen powers of 2 to see if there’s a simple pattern.

When n isn’t a power of 2 you need to use Nim-values associated with infinite ordinals but that’s okay since they’re well-ordered.

Jim Propp

On Mon, Jan 18, 2021 at 7:23 AM Joerg Arndt <arndt@jjj.de> wrote:

...

Possibly making a fool of myself... Have you checked 'the Bible' (Lidl, Niederreiter)? I seem to recall that there is a nontrivial amount of coverage about binomial polynomials, specifically regarding irreducibility.

Best regards, jj

...

Let $n = 2^{e_0} q_1^{e_1} \cdots q_i^{e_i}$ be the prime factorization of $n$. Let $p$ be an odd prime. Is it true that $\exists k$ such that $x^n+k$ is irreducible over GF($p$) $\iff$ $(2^{min(e_0,2)} q_1 \cdots q_i) | (p-1)$ ?

Are there similar criteria for "larger" polynomials such as $x^n + k_1 x

* Mike Speciner <ms@alum.mit.edu> [Jan 14. 2021 17:11]: +

...

k_0$ ?

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

---

math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

The lex-least minimal polynomial for GF[256] is x8 + x4 + x3 + x + 1 (eliding the ^s). This is used in AES. sketch: We need the minimal irreducible-mod2 of degree 8. The poly must include x^8 to get the degree right. It must include x^0 (or it's a multiple of x). It must have odd Hamming weight (or it's a multiple of x+1). There are no irreducible trinomials for GF[256^N] (Stickleberger's theorem, I don't know the details); or, by cases: x^8 + x^even + 1 is a square of x^4 + x^(even/2) + 1; x^8 + x + 1 is a multiple of x^2 + x + 1, which divides x^3 + 1; x^8 + x^3 + 1 is a multiple of x^3 + x + 1, which divides x^7 + 1. x^8 + x^5 + 1 and x^8 + x^7 + 1 are excluded by degree symmetry. Next up are pentanomials: x^8 + x^3 + x^2 + x + 1 is a multiple of x^3 + x^2 + 1, which divides x^7 + 1. x^8 + x^4 + x^2 + x + 1 is a multiple of x^4 + x^3 + x^2 + x + 1, which divides x^5 + 1. To verify irreducibility of the AES polynomial, you need to exclude the possible divisors of degree <=4. The primes are (exponents only) 1, 10, 210, 310, 320, 410, 430, 43210. Most of these are excludable "by inspection" based on other multiples identified above: consider 210. It's a divisor of 810 above; the AES poly is 84310; if it's divisible by 210, so is (84310 xor 810) = 43 = 3 * 10, nope. The exception is 410 * 430, but that product includes an x^7 term, fail. Overall, there are (256-16)/8 = 30 irreducible octic polys. Rich ------ Quoting James Propp <jamespropp@gmail.com>:

The the first nine powers of *16 (according to https://www.math.ucla.edu/~tom/NimProd.html) are *1, *16, *24, *152, *21, *72, *203, *118, and *31. In base 2 these are represented by the rows of the matrix {{0,0,0,0,0,0,0,1}, {0,0,0,1,0,0,0,0}, {0,0,0,1,1,0,0,0}, {1,0,0,1,1,0,0,0}, {0,0,0,1,0,1,0,1}, {0,1,0,0,1,0,0,0}, {1,1,0,0,1,0,1,1}, {0,1,1,1,0,1,1,0}, {0,0,0,1,1,1,1,1}} whose mod-2 annihilator is [1,1,0,1,1,1,1,0,1], so the minimal polynomial of *16 (if I haven't goofed) is x^8 + x^6 + x^5 + x^4 + x^3 + x + 1.

Jim Propp

On Mon, Jan 18, 2021 at 6:17 PM James Propp <jamespropp@gmail.com> wrote:

...

See https://en.m.wikipedia.org/wiki/Nimber . Conway?s definition of multiplication gives us a way to view the finite nimbers *0, *1, *2, *3, *4, ... as the nested union of GF(2), GF(4), GF(16), GF(256), etc.

The elements of GF(4) are *0, *1, *2, and *3, and the ?first? element of GF(16) that isn?t in GF(4) is *4. For what irreducible polynomial p( ) over GF(2) do we have p(x) = 0 when x = *4? Putting x = *4 we compute x^2 = *6 (this is the discovery that made Conway wiggle his legs in the air in delight), x^3 = *14, and x^4 = *5, giving x^4 + x^1 + x^0 = *5 + *4 + *1 = *0. So the minimal polynomial of *8 in GF(16) is x^4+x+1.

To bring GF(8) etc. into the game, we need to extend the game to nimbers associated with countable ordinals. As I recall, *omega is a cube root of *2.

Jim Propp

On Mon, Jan 18, 2021 at 5:33 PM Mike Speciner <ms@alum.mit.edu> wrote:

...

Yes, those are the lexicographically smallest. Were you asking for the ones with fewest terms? Something else? It wasn't clear to me.

Just done with a brute-force search. (I wrote some code a while back when I was playing with finite fields for a demonstration of secret sharing. Ended up with a python library with classes for such things as finite fields, rationals/complex rationals/quaternion rationals, matrices, polynomials. (https://github.com/ms0/pymath)

The question I asked at the start of this thread was really about short-circuiting that brute-force search a bit, at least for odd characteristic. I'm testing with the deterministic Rabin irreducibility test. Of course, I can easily generate a similar table for other primes. (Python isn't fast, but it's easy to code in; the p=2 case does everything with bitwise operations, so it's not as slow as it could be.)

On 18-Jan-21 16:43, James Propp wrote:

Thanks, Mike!

Looks like you tackled all the Galois fields GF(2^n), not just GF(2^(2^k)). How did you do it?

Let me make sure I understand your notation. Does GF2_15_11 mean the polynomial 1 + x + x^15?

I am surprised that the bit strings you found are so short (corresponding to most of the high-degree coefficients being zero). It makes me wonder whether you answered a different question than the one I asked, and computed the lexicographically first irreducible polynomial of degree n. That?s an interesting question too, but I see no reason why they should have the same answer.

Jim Propp

On Mon, Jan 18, 2021 at 3:35 PM Mike Speciner <ms@alum.mit.edu> wrote:

...

Here's the first 64, with the x^n term elided; constant term last. Not an obvious pattern, and, interpreted as a binary number, not in OEIS (either with or without the x^n term)...

'GF2_2_0' 'GF2_2_11' 'GF2_3_11' 'GF2_4_11' 'GF2_5_101' 'GF2_6_11' 'GF2_7_11' 'GF2_8_11011' 'GF2_9_11' 'GF2_10_1001' 'GF2_11_101' 'GF2_12_1001' 'GF2_13_11011' 'GF2_14_100001' 'GF2_15_11' 'GF2_16_101011' 'GF2_17_1001' 'GF2_18_1001' 'GF2_19_100111' 'GF2_20_1001' 'GF2_21_101' 'GF2_22_11' 'GF2_23_100001' 'GF2_24_11011' 'GF2_25_1001' 'GF2_26_11011' 'GF2_27_100111' 'GF2_28_11' 'GF2_29_101' 'GF2_30_11' 'GF2_31_1001' 'GF2_32_10001101' 'GF2_33_1001011' 'GF2_34_11011' 'GF2_35_101' 'GF2_36_110101' 'GF2_37_111111' 'GF2_38_1100011' 'GF2_39_10001' 'GF2_40_111001' 'GF2_41_1001' 'GF2_42_100111' 'GF2_43_1011001' 'GF2_44_100001' 'GF2_45_11011' 'GF2_46_11' 'GF2_47_100001' 'GF2_48_101101' 'GF2_49_1110001' 'GF2_50_11101' 'GF2_51_1001011' 'GF2_52_1001' 'GF2_53_1000111' 'GF2_54_1111101' 'GF2_55_1000111' 'GF2_56_10010101' 'GF2_57_10001' 'GF2_58_1100011' 'GF2_59_1111011' 'GF2_60_11' 'GF2_61_100111' 'GF2_62_1101001' 'GF2_63_11' 'GF2_64_11011'

On 18-Jan-21 12:01, James Propp wrote:

...

If I?m not mistaken, Conway?s notion of Nim-multiplication gives a way of singling out a ?first? degree n irreducible polynomial over GF(2). For instance, x = *4 satisfies x^2 = *6, x^3 = *14, and x^4 = *5, so the first irreducible polynomial of degree 4 is x^4 + x + 1.

It would be interesting to peruse these polynomials for the first dozen powers of 2 to see if there?s a simple pattern.

When n isn?t a power of 2 you need to use Nim-values associated with infinite ordinals but that?s okay since they?re well-ordered.

Jim Propp

On Mon, Jan 18, 2021 at 7:23 AM Joerg Arndt <arndt@jjj.de> wrote:

...

Possibly making a fool of myself... Have you checked 'the Bible' (Lidl, Niederreiter)? I seem to recall that there is a nontrivial amount of coverage about binomial polynomials, specifically regarding irreducibility.

Best regards, jj

* Mike Speciner <ms@alum.mit.edu> [Jan 14. 2021 17:11]: > Let $n = 2^{e_0} q_1^{e_1} \cdots q_i^{e_i}$ be the prime factorization of > $n$. > Let $p$ be an odd prime. > Is it true that > $\exists k$ such that $x^n+k$ is irreducible over GF($p$) $\iff$ > $(2^{min(e_0,2)} q_1 \cdots q_i) | (p-1)$ ? > > Are there similar criteria for "larger" polynomials such as $x^n + k_1 x + > k_0$ ? > > > _______________________________________________ > math-fun mailing list > math-fun@mailman.xmission.com > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

---

math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun