[seqfan] Re: OT: telling one-to-one polynomial maps in a finite field

[Joerg Arndt]

* Georgi Guninski <guninski at guninski.com> [May 17. 2010 15:05]:
> Sorry for Off-Topic, my pain is:
> 
> Is it possible to *efficiently* (probabilistically) tell if a polynomial map K^n -> K^n is one-to-one where K is a *finite field* ?
> 
> If the jacobian matrix (or some modification of it) makes sense in a finite field probably it is possible.
> 
> The specific case i am interested is the MD5 crypto hash function restricted to 128 bit input - this is a polynomial map: GF(2)^128 -> GF(2)^128.
> 
> A cryptographer told me it is an open question if it is one-to-one (no known 128 bit collisions).
> Some numerical experiments with the jac. matrix suggest it is not one-to-one.
> 
> Thank you.
> 

Not sure if a map GF(2)^n -> GF(2)^n can (efficiently, computationally)
be expressed as a map GF(2^n) -> GF(2^n).  If so, check the literature
for 'permutation polynomial'.