2

I am learning multiplication in finite fields, and would like to clarify a few basic concepts:

First: Is there a standard mapping between (regular) integers and elements of a finite field? For example, consider the integers and the finite field $GF(2^8)$. Then $0$ the integer corresponds to $0$ in the finite field. $1$ corresponds to $x^0$, $2$ to $x^1$, $3$ to $x^1 + x^0$, $4$ to $x^2$. Is there a standard term for this?

(SAGE math seems to implement this mapping via fetch_int and integer_representation.)

Second: Integers $p,q,r < 2^n$ meet $pq = r$. Let $m(p)$ be the mapping of $p$ to $GF(2^{2n})$ similar to how I described. Then it follows that $m(p)*m(q) = m(r)$. This is true because $r$ is small enough that it need not be reduced. Is that correct?

If I am making a basic mistake, please explain: I am new to finite fields.

SRobertJames
  • 4,278
  • 1
  • 11
  • 27
  • 2
    What is x in your question and which construction of finite field of $2^8$ do you use here? – Invincible Jan 16 '22 at 21:20
  • @Vladislav I indeed used $x$ two different ways; fixed now: $x$ is the variable in the field's polynomial. If I understand the 2nd question, $GF(2^8)$ is expressed using $?x^8 + ?x^7 ... + ?x^1 + ?x^0$, where each ? is either 1 or 0. – SRobertJames Jan 16 '22 at 21:23

1 Answers1

1

First, apparently Sage does not map from integers to finite fields in a way that preserves multiplication, even for smallish integers or field elements. For example,

sage: $k = GF(2**4, repr='int' )

sage: a = k.gen()

sage: a

2

sage: a*a

4

sage: (1+a)*(1+a)

5

Yes, multiplication in finite fields $GF(p^n)$ can be modeled by multiplication of polynomials (modulo some suitable irreducible), but the coefficients of the polynomials must be considered to be in $GF(p)$.

Even if there are some coincidental matches $m(a)*m(b)=m(ab)$, I don't think this is something to hope for, or attempt to use. It is certainly not a good explanation of multiplication in $GF(p^n)$, in any case. There's really no good relationship between the set $\{0,1,2,\ldots,p^n-1\}$ and $GF(p^n)$, except that they have the same number of elements.

paul garrett
  • 52,465
  • If $p = 2$, isn't the correspondence quite close? When multiplying by hand, I get $ab_1 = a_1 * b_0 + a_0*b_1$, which seems to hold true on both sides. If I'm off, could you please elaborate? – SRobertJames Jan 17 '22 at 02:36
  • Well, yes, for low-degree elements (for a given generator), there is some matching, but it's imperfect, and does not last long. I'd really recommend not insisting on this, but thinking about multiplying polynomials in "x", with coefficients in $\mathbb F_p$, and dividing-with-remainder by the polynomial used to defined the finite field. The Sage documentation tells something about their choices... Finite fields are simply different things than integers-mod-$n$. – paul garrett Jan 17 '22 at 03:14