[math-fun] Synthesizing functions over finite fields with polynomials
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?
Since a function over a finite field GF(p^k) has only p^k inputs, there's trivially a degree p^k - 1 polynomial that goes through each of those points. On Wed, Aug 22, 2012 at 9:06 AM, 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?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
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?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- 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
participants (3)
-
Henry Baker -
Mike Stay -
Neil Sloane