## Phase Transition of Multivariate Polynomial Systems

##### File(s)

##### Date

2006##### Author

Fusco, Giordano

Bach, Eric

##### Publisher

University of Wisconsin-Madison Department of Computer Sciences

##### Metadata

Show full item record##### 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.