Re: [math-fun] Synthesizing functions over finite fields with polynomials
OK, let's now look specifically at functions which are _permutations_. Suppose I have a finite field GF(p^k), which can be represented as k-element vector with elements [0..p-1]. Is there any characterization of these Lagrange interpolations that happen to generate only permutations? I.e., let P={x|x=[x0,x1,x2,...,x(k-1)] and 0<=xi<p and i/=j => xi/=xj}, then f(p)=q for p,q in P. Alternately, which algebraic constructions generate _only_ and _all_ permutations of [0..p-1]. Obviously additions and multiplications by constants generate some of the permutations, but not all of them. What else do we need to get all of the permutations? At 09:24 AM 8/22/2012, Neil Sloane wrote:
Sure, use a version of Lagrange interpolation. Make a list (a generalized truth table) of all the values the function takes at all possible arguments. Then write a monomial for each term and add them up. E.g. if you want the value 7 at x=3, y=4, z=5, the monomial is Prod_{a!=3}(x-a) Prod_{b!=4} (y-b) Prod_{c!=5) (z-c) 7/d, where d is the appropriate constant.
On Wed, Aug 22, 2012 at 12:06 PM, Henry Baker <hbaker1@pipeline.com> wrote:
It appears that all functions over GF(2) can be synthesized using only polynomials:
E.g.,
f()=0, f()=1
f(x)=0, f(x)=1, f(x)=x, f(x)=1+x
not(x)=1+x, and(x,y)=x*y, or(x,y)=x+y+x*y, etc.
Q: Can all functions over _any_ finite field by synthesized using only polynomials, and is there a simple synthesis procedure?
-- Dear Friends, I have now retired from AT&T. New coordinates:
Neil J. A. Sloane, President, OEIS Foundation 11 South Adelaide Avenue, Highland Park, NJ 08904, USA Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
P.S., obviously we need k=p, in order to get permutations. Also, addition by non-zero constant * [1,1,1,...,1], rather than simply addition by constant. At 08:09 AM 2/23/2014, Henry Baker wrote:
OK, let's now look specifically at functions which are _permutations_.
Suppose I have a finite field GF(p^k), which can be represented as k-element vector with elements [0..p-1].
Is there any characterization of these Lagrange interpolations that happen to generate only permutations?
I.e., let P={x|x=[x0,x1,x2,...,x(k-1)] and 0<=xi<p and i/=j => xi/=xj}, then f(p)=q for p,q in P.
Alternately, which algebraic constructions generate _only_ and _all_ permutations of [0..p-1].
Obviously additions and multiplications by constants generate some of the permutations, but not all of them.
What else do we need to get all of the permutations?
At 09:24 AM 8/22/2012, Neil Sloane wrote:
Sure, use a version of Lagrange interpolation. Make a list (a generalized truth table) of all the values the function takes at all possible arguments. Then write a monomial for each term and add them up. E.g. if you want the value 7 at x=3, y=4, z=5, the monomial is Prod_{a!=3}(x-a) Prod_{b!=4} (y-b) Prod_{c!=5) (z-c) 7/d, where d is the appropriate constant.
On Wed, Aug 22, 2012 at 12:06 PM, Henry Baker <hbaker1@pipeline.com> wrote:
It appears that all functions over GF(2) can be synthesized using only polynomials:
E.g.,
f()=0, f()=1
f(x)=0, f(x)=1, f(x)=x, f(x)=1+x
not(x)=1+x, and(x,y)=x*y, or(x,y)=x+y+x*y, etc.
Q: Can all functions over _any_ finite field by synthesized using only polynomials, and is there a simple synthesis procedure?
-- Dear Friends, I have now retired from AT&T. New coordinates:
Neil J. A. Sloane, President, OEIS Foundation 11 South Adelaide Avenue, Highland Park, NJ 08904, USA Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
* Henry Baker <hbaker1@pipeline.com> [Feb 23. 2014 18:10]:
OK, let's now look specifically at functions which are _permutations_.
Suppose I have a finite field GF(p^k), which can be represented as k-element vector with elements [0..p-1].
Is there any characterization of these Lagrange interpolations that happen to generate only permutations?
There is quite some literature about that problem, search for "permutation polynomials" finite field Best, jj
[...]
Just today: "Permutation trinomials over finite fields with even characteristic" http://arxiv.org/abs/1402.5734 On page 2: "To the best of the authors' knowledge, the following is a list of known classes of permutation trinomials over F_{2^m}:" (6 items follow). * Joerg Arndt <arndt@jjj.de> [Feb 23. 2014 19:48]:
* Henry Baker <hbaker1@pipeline.com> [Feb 23. 2014 18:10]:
OK, let's now look specifically at functions which are _permutations_.
Suppose I have a finite field GF(p^k), which can be represented as k-element vector with elements [0..p-1].
Is there any characterization of these Lagrange interpolations that happen to generate only permutations?
There is quite some literature about that problem, search for "permutation polynomials" finite field
Best, jj
[...]
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (2)
-
Henry Baker -
Joerg Arndt