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

Georgi Guninski guninski at guninski.com
Mon May 17 10:54:15 CEST 2010

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.

More information about the SeqFan mailing list