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.
Subscribe to:
Post Comments (Atom)
2x^2+x is 1-1 mod 4.
ReplyDelete2x²+x is 1–1 mod any power of 2.
DeleteRivest has shown in 1999 that polynomial ∑aᵢxⁱ is a permutation mod 2ⁿ iff a₁ is odd, (a₂+a₄+a₆+⋯) is even, and (a₃+a₅+a₇+⋯) is even.
This comment has been removed by a blog administrator.
ReplyDeleteThese polynomials are known as permutation polynomials in the literature. Testing if f in 1-1 mod m reduces to testing if for every prime factor of p, f in 1-1 mod p and f' has no root mod p (see for instance Theorems 2 and 6 of http://arxiv.org/abs/math/0509523). Both tests can be achieved in deterministic polytime (see http://eccc.hpi-web.de/report/2005/008/ for the first one, and the second one is classical). Thus given the prime factorization of m, the test is deterministic polytime. This does not imply that it is "easy" ;-).
ReplyDeleteThese polynomials are known as permutation polynomials in the literature. Testing if f in 1-1 mod m reduces to testing if for every prime factor of p, f in 1-1 mod p and f' has no root mod p (see for instance Theorems 2 and 6 of http://arxiv.org/abs/math/0509523). Both tests can be achieved in deterministic polytime (see http://eccc.hpi-web.de/report/2005/008/ for the first one, and the second one is classical). Thus given the prime factorization of m, the test is deterministic polytime. This does not imply that it is "easy" ;-).
ReplyDeleteTo elaborate a little bit:
ReplyDeleteQuadratic polynomials are never 1-1 over a field of characteristic different from 2 (because a non-zero element has 0 or 2 square roots).
Over GF(2^r): x^2 is 1-1 but unless I am mistaken, a polynomial with a linear term will not be 1-1 (you have 0 or 2 preimages).
If you start counting mod n for composite n there are other 1-1 polynomials (like in the above example).
Might this problem somehow be connected to whether the polynomial f(x) has roots mod n? At least in some cases this might lead us to a partial solution:
ReplyDeleteSince we assume that the constant c is zero, we know that the polynomial has at least the root 0. If the polynomial has another root y, then it is obviously not 1-1.
Finding out if the polynomial has roots may be fast in some cases. If n is of the form p^k, where p is a prime, then we may use factorization algorithms for polynomials over finite fields (see for instance https://en.wikipedia.org/wiki/Factorization_of_polynomials_over_finite_fields). If the degree d of the polynomial is small in relation to n, then we might find an algorithm that is faster than O(n). For instance if n is a prime, then Shoup's algorithm (http://www.shoup.net/papers/detfac.pdf) can factorize the polynomial in time O(n^0.5*(log n)^2*d^(2+eps)). Since the polynomial may have at most d factors, it should be easy to find any linear factors (if d is small in relation to n)
This is of course only a partial solution, since everything above only works for finite fields (or at least all the analysis is done over finite fields). I'm also sure that there is a polynomial that is not 1-1 and does not have more than one root; an example of a polynomial like this would of course be nice!
It appears that testing whether a polynomial over a finite field is a permutation polynomial is, in fact, in P.
ReplyDeleteIt is called permutation polynomials. It is a very important research problem. There are tons of survey on this topics. Start with wikipedia first.
ReplyDeleteSee the notes and references here. The problem is apparently in ZPP.
ReplyDeleteOr indeed in P: http://eccc.hpi-web.de/report/2005/008/download/
ReplyDelete