Loading...
Please wait, while we are loading the content...
Similar Documents
Testing Algebraic Independence Of Polynomials Over Finite Fields
| Content Provider | Semantic Scholar |
|---|---|
| Author | Sinhababu, Amit |
| Abstract | We consider the problem of testing algebraic independence of a set of polynomials over finite fields of small characteristic. Algebraic independence of polynomials is a nonlinear generalization of linear independence of polynomials. Over fields of zero characteristic, a set of polynomials is algebraically independent if and only if the Jacobian matrix of the polynomials has full rank, and this can be tested in randomized polynomial time. But over fields of small characteristic, Jacobian criterion does not work and designing an efficient criterion to test algebraic independence is an open problem till now. In this thesis, we explore new approaches towards finding such a criterion. Over fields of small characteristic, if Jacobian of a set of polynomials is nonzero, then we conclude that they are algebraically independent. If the Jacobian is zero, the polynomials need not be algebraically dependent. We try to transform the algebraically independent polynomials for which the Jacobian is zero such that the Jacobian of the transformed polynomials is nonzero. Using this approach, we solve the special case of efficiently testing algebraic independence of two bivariate binomials over Fp . Pursuing a different approach, we come up with a new characterization of algebraic independence over Fp. We lift the polynomials by adding polynomials whose coefficients are multiples of p. We prove that if the two polynomials are algebraically dependent, then the p-adic valuation of the Jacobian of these polynomials can be arbitrarily increased by suitable lifting of the polynomials, but if the polynomials are algebraically independent then the p-adic valuation of the Jacobian cannot be increased by lifting beyond a fixed bound. One part of the proof uses Witt Jacobian [MSS12] criterion, the other part uses the observation that the annihilating polynomial's p-adic valuation can be arbitrarily increased by lifting the polynomials. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.cse.iitk.ac.in/users/nitin/theses/sinhababu-2014.pdf |
| Alternate Webpage(s) | https://www.cse.iitk.ac.in/users/nitin/theses/sinhababu-2014.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
