tag:blogger.com,1999:blog-3722233.post193902680920835467..comments2023-12-07T03:00:23.146-06:00Comments on Computational Complexity: Is determining if a poly over a finite field is 1-1 hard? Sure seems so.Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-3722233.post-39672202154586296372016-07-13T07:18:06.185-05:002016-07-13T07:18:06.185-05:002x²+x is 1–1 mod any power of 2.
Rivest has shown ...2x²+x is 1–1 mod any power of 2.<br />Rivest 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-57838120709572569352016-07-06T09:48:49.698-05:002016-07-06T09:48:49.698-05:00Or indeed in P: http://eccc.hpi-web.de/report/2005...Or indeed in P: http://eccc.hpi-web.de/report/2005/008/download/Naradnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11149702778887034182016-07-06T09:33:16.424-05:002016-07-06T09:33:16.424-05:00See the notes and references here. The problem is...See the notes and references <a href="https://en.wikipedia.org/wiki/Permutation_polynomial" rel="nofollow">here</a>. The problem is apparently in ZPP.Naradnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86446534853541662352016-07-06T01:16:57.260-05:002016-07-06T01:16:57.260-05:00It is called permutation polynomials. It is a very...It is called permutation polynomials. It is a very important research problem. There are tons of survey on this topics. Start with wikipedia first.Qihttps://www.blogger.com/profile/07459602007747656961noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49581441825063241832016-07-05T15:26:36.931-05:002016-07-05T15:26:36.931-05:00It appears that testing whether a polynomial over ...It appears that testing whether a polynomial over a finite field is a permutation polynomial <a href="http://eccc.hpi-web.de/report/2005/008/" rel="nofollow">is, in fact, in P.</a>Andrewnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58310659049361274152016-07-05T12:14:21.240-05:002016-07-05T12:14:21.240-05:00Might this problem somehow be connected to whether...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:<br /><br />Since 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. <br /><br />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)<br /><br />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!Sebastian Björkqvisthttp://www.sebastianbjorkqvist.com/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-40894076116468114082016-07-05T10:31:08.368-05:002016-07-05T10:31:08.368-05:00To elaborate a little bit:
Quadratic polynomials ...To elaborate a little bit:<br /> Quadratic polynomials are never 1-1 over a field of characteristic different from 2 (because a non-zero element has 0 or 2 square roots).<br />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).<br />If you start counting mod n for composite n there are other 1-1 polynomials (like in the above example).Pascalhttps://www.blogger.com/profile/14201150679841329835noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17379733225680600262016-07-05T08:22:48.742-05:002016-07-05T08:22:48.742-05:00These polynomials are known as permutation polynom...These 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" ;-).Brunohttps://www.blogger.com/profile/12862262125220926610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22713394991144931802016-07-05T08:17:35.422-05:002016-07-05T08:17:35.422-05:00These polynomials are known as permutation polynom...These 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" ;-).Brunohttps://www.blogger.com/profile/12862262125220926610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49242140925859551192016-07-05T08:17:08.308-05:002016-07-05T08:17:08.308-05:00This comment has been removed by a blog administrator.Brunohttps://www.blogger.com/profile/12862262125220926610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87399907988237623012016-07-05T03:58:28.618-05:002016-07-05T03:58:28.618-05:002x^2+x is 1-1 mod 4.2x^2+x is 1-1 mod 4.Pascalhttps://www.blogger.com/profile/14201150679841329835noreply@blogger.com