Re: Question about "polynomial evaluations"

In article
<a910f988-7739-4061-8885-788d571ac913@xxxxxxxxxxxxxxxxxxxxxxxxxxx>,
Brian Chandler <imaginatorium@xxxxxxxxxxxxx> wrote:

Arturo Magidin wrote:
On Jun 17, 2:16 pm, Brian Chandler <imaginator...@xxxxxxxxxxxxx>
wrote:

<snipped>

Yes; what I think you were aiming for is what I mentioned elsewhere:
polynomial functions as opposed to polynomials.

Ah, yes. Thanks -- your explanation made a lot of it clearer.

In fact, one can prove that if R is *any* finite field, then *every*
element of F(R) is a polynomial function; in particular, since F(R) is
finite, the map eval cannot be one-to-one.

Is this proof trivial? It looks as though you can just "construct" a
polynomial for any function, given an unlimited amount of "space" to
play with. Intuitively, it ought to be possible to make a polynomial
(function) that maps p to q, and everything except p to 0, then you
just add them together. [?]

Just use Lagrange interpolation polynomial.

For example, let R be a finite field with the three elements 0, 1, 2.
Let f be a function in F(R).
Then,

f(x) = (x-1)(x-2)*f(0) + (x-0)(x-2)*f(1) + (x-0)(x-1)*f(2)
---------- --------- ---------
(0-1)(0-2) (1-0)(1-2) (2-0)(2-1)

The right hand side is a polynomial of degree 2.
Check both sides agree for x = 0, 1, 2.
.

Relevant Pages

  • Re: Looking for algorithm
    ... > sequence of C's as your checksum.) ... My pitiful finite field knowledge is being sorely tested, ... I've used PARI/GP to test a few polynomials, to see how well I understood ... For example for ring operations I use "modulo the polynomial ...
    (sci.crypt)
  • Re: Properties of polynomials over finite fields
    ... > multivariate polynomials over a finite field F in their proofs. ... > from the affine space F^k to the field F and make various claims about ...
    (sci.math.research)
  • Re: Public Key, Symbolic Calculation
    ... that polynomials with coefficients in Q are really the same as ... But the algebraics over Z are not a finite field, ... explained by someone who isn't a professional mathematician. ... would "get" this Berlekemp method, if it were written more clearly. ...
    (sci.crypt)
  • Re: Nomenclature question
    ... >However I am not sure that the context really resolves this. ... >Hence, for example, there are six second order polynomials that do not ... I still do not like the wording. ... Suppose we have a finite field F, a finite extension field E of F, ...
    (sci.crypt)
  • Re: Properties of polynomials over finite fields
    ... tim_ptacek@pobox.com (Tim Ptacek) wrote: ... > multivariate polynomials over a finite field F in their proofs. ...
    (sci.math)