Phase Transition of Multivariate Polynomial Systems

Abstract

A random multivariate polynomial system with more equations than variables is likely to be unsolvable. On the other hand if there are more variables than equations, the system has at least one solution with high probability. In this paper we study in detail the phase transition between these two regimes, which occurs when the number of equations equals the number of variables. In particular the limiting probability for no solution is 1/e at the phase transition, over a prime field.

We also study the probability of having exactly s solutions, with s >= 1. In particular, the probability of a unique solution is asymptotically 1/e if the number of equations equals the number of variables. The probability decreases very rapidly if the number of equations increases or decreases.}

Our motivation is that many cryptographic systems can be expressed as large multivariate polynomial systems (usually quadratic) over a finite field. Since decoding is unique, the solution of the system must also be unique. Knowing the probability of having exactly one solution may help us to understand more about these cryptographic systems. For example, whether attacks should be evaluated by trying them against random systems depends very much on the likelihood of a unique solution.