Abstract
We investigate the complexity of the following polynomial solvability problem: Given a finite field \({\mathbb F}_{q}\) and a set of polynomials
determine the \({\mathbb F}_{q}\)-solvability of the system
We give a deterministic polynomial-time algorithm for this problem.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Gao, S., Kaltofen, E., Lauder, A.: Deterministic distinc-degree factorization of polnomials over finite fields. Journal of Symbolic Computing 38(6), 1461–1470 (2004)
Huang, M.-D., Wong, Y.-C.: Solvability of systems of polynomial congruences modulo a large prime. Computational Complexity 8(3), 227–257 (1999)
Lidl, R., Mullen, G.L.: When does a polynomial over a finite field permute the elements of the field? American Mathematical Monthly 95, 243–246 (1988)
Lidl, R., Mullen, G.L.: When does a polynomial over a finite field permute the elements of the field?, II. American Mathematical Monthly 100, 71–74 (1993)
Lidl, R., Muller, W.B.: Permutation Polynomials in RSA cryptosystems. In: Chaum, D. (ed.) Proceedings CRYPTO 1983, pp. 293–301 (1983)
Ma, K., Von Zur Gathen, J.: The computational complexity of recognizing permutation functions. Computational Complexity 5(1), 76–97 (1995)
Lenstra, H.: Private Communication (2005)
Rivest, R.L., Shamir, A., Adleman, L.M.: A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM 21(2), 120–126 (1978)
Bach, E.: Weil bounds for singular curves. Applicable Algebra in Engineering, Communication and Computing 7, 289–298 (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kayal, N. (2005). Solvability of a System of Bivariate Polynomial Equations over a Finite Field. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds) Automata, Languages and Programming. ICALP 2005. Lecture Notes in Computer Science, vol 3580. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11523468_45
Download citation
DOI: https://doi.org/10.1007/11523468_45
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-27580-0
Online ISBN: 978-3-540-31691-6
eBook Packages: Computer ScienceComputer Science (R0)