Monday, July 04, 2016
Is determining if a poly over a finite field is 1-1 hard? Sure seems so.
When I teach cryptography to High School students I begin with shift and linear ciphers which are
x --> x+s mod 26 (s is a shift, x is a letter of the alphabet. Hmm- x really IS a letter of the alphabet!)
x--> ax+b mod 26 (Note that a has to be rel prime to 26.)
I then ask why nobody seems to have ever used
x --> ax2 + bx + c mod 26.
I then tell them that this is because there is no quick test that will, given (a,b,c), tell if
f(x) = ax2 + bx + c mod 26 is 1-1 (and hence onto).
It recently dawned on me that I don't really know that its hard to test.
(ADDED LATER) In fact its not true. Algebra shows that f(x) is NOT 1-1 iff
a(x+y)+b =0 mod 26
has a solution. If a is rel prime to 26 then clearly there is a solution (many in fact).
If a is not rel prime to 26 then I suspect this is not hard.
How hard is the following problem?
Given a poly f(x) of degree d, and n, is f(x) mod n 1-1?
We will assume all coefficients are between 0 and n.. We can also assume that c is 0 since f(x) is 1-1 then f(x)-c is 1-1.
The coefficients are given in binary so the length of the input is roughly dlog(n).
One can of course compute f(0), f(1),...,f(n-1) and see if there are any repeats, but this takes O(n) steps which is exp in the input of length log n.
I suspect that this is either a well known solved problem (either in P or NPC) or a well known open problem. Any help or references will be more appreciated than usual-- see next paragraph.
I am the new SIGACT News Open Problems Column editor. In the future I will be soliciting people to write columns for me, but the first one I'll do myself and this might be a good topic- if its open! And if it is open, would be good to know references and what is known.