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