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

Joerg Arndt arndt at jjj.de
Mon May 17 18:35:44 CEST 2010

* 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'.

More information about the SeqFan mailing list