Ah, there it is! Thanks for the link! I'm looking forward to catch up!
I just recently noticed that I thought for yours I knew how finite fields worked, but actually didn't.
Addition ist dead easy, there's just one field for any finite order, the primes are cyclic, prime powers come from Galois extensions, so they must be like vectors over prime fields, right? Any other way to get a field of order n is going to be isomorphic.
Well, of course not. For one, F_p^2 doesn't have twice as many elements as F_p (unless p=2). It says square, not double! The elements of F_p^n are the polynomials of degree n-1. But then that's still not all!
To write up a multiplication table we need to pick an irreducible polynomial P of degree n, so that when we multiply two elements of our field, we can use P=0 to bring down the degree of our product back to the allowed range.
And here's the kicker I totally missed for more than a decade: The labeling of F_p^n depends on our choice of P! There's even an especially nice kind of canonical polynomials for this purpose.
These are called Conway polynomials, and were invented by R. Parker. They are quite difficult to compute so current computer algebra systems use precomputed tables of them, so they can label GF(q)'s elements consistently.
npub1knzsux7p6lzwzdedp3m8c3c92z0swzc0xyy5glvse58txj5e9ztqpac73p (npub1knz…c73p)
Refurio Anachro /
npub1el…rne8q
2023-10-07 12:15:15
in reply to nevent1q…28r9
Author Public Key
npub1ell2tqnyt68yqkyrpxez3y4hm86k49ns3mu2ajhq09elwhuf9hus5rne8qPublished at
2023-10-07 12:15:15Event JSON
{
"id": "1a88683e60e59d9ee34e9105e3441080368602f740df8eb66349e8f2f86868e8",
"pubkey": "cffea582645e8e40588309b22892b7d9f56a96708ef8aecae07973f75f892df9",
"created_at": 1696680915,
"kind": 1,
"tags": [
[
"p",
"b4c50e1bc1d7c4e1372d0c767c4705509f070b0f3109447d90cd0eb34a992896",
"wss://relay.mostr.pub"
],
[
"p",
"f7346eb283902ada9d21c109a93e83128d9f87d8fcfe70ad819b3bf2ad9bce16",
"wss://relay.mostr.pub"
],
[
"e",
"d0e6ef68938067fa98ba7733cb5bf4d16f3ffb4b3a2f2a8887e35d1755352999",
"wss://relay.mostr.pub",
"reply"
],
[
"proxy",
"https://mathstodon.xyz/users/RefurioAnachro/statuses/111193680481892386",
"activitypub"
]
],
"content": "Ah, there it is! Thanks for the link! I'm looking forward to catch up!\n\nI just recently noticed that I thought for yours I knew how finite fields worked, but actually didn't.\n\nAddition ist dead easy, there's just one field for any finite order, the primes are cyclic, prime powers come from Galois extensions, so they must be like vectors over prime fields, right? Any other way to get a field of order n is going to be isomorphic.\n\nWell, of course not. For one, F_p^2 doesn't have twice as many elements as F_p (unless p=2). It says square, not double! The elements of F_p^n are the polynomials of degree n-1. But then that's still not all!\n\nTo write up a multiplication table we need to pick an irreducible polynomial P of degree n, so that when we multiply two elements of our field, we can use P=0 to bring down the degree of our product back to the allowed range.\n\nAnd here's the kicker I totally missed for more than a decade: The labeling of F_p^n depends on our choice of P! There's even an especially nice kind of canonical polynomials for this purpose.\n\nThese are called Conway polynomials, and were invented by R. Parker. They are quite difficult to compute so current computer algebra systems use precomputed tables of them, so they can label GF(q)'s elements consistently.\n\nnostr:npub1knzsux7p6lzwzdedp3m8c3c92z0swzc0xyy5glvse58txj5e9ztqpac73p",
"sig": "7e8e1418d7a54a95a04bf4b10440c42c32d3afb882b7b3c7c8ba8fb320b6e1dba3693f04cc5c69ee7db8278f09526aaa0441e94487bfee213e7c10e1d8563da8"
}