In this paper we introduce a new type of probabilistic search algorithm, which we call the
{\it Bellagio} algorithm: a probabilistic algorithm which is guaranteed to run in expected polynomial time,
and to produce a correct and {\it unique} solution with high probability.
We argue the applicability of such algorithms for
the problems of verifying delegated computation in a distributed setting, and for generating
cryptographic public-parameters and keys in distributed settings.
We exhibit several examples of Bellagio algorithms for problems
for which no deterministic polynomial time algorithms are known.
In particular,we show such algorithms for:
\begin{itemize}
\item finding a unique generator
for \Z\ when $p$ is a prime of the form $kq+1$ for $q$ is prime and $k = \polylog(p)$.
The algorithm runs in expected polynomial in $\log p$ time.
\item finding a
unique $q$'th non-residues of \Z\ for any prime divisor $q$ of $p-1$,
extending Lenstra's \cite{L} algorithm for finding unique quadratic non-residue of \Z.
The algorithm runs in expected polynomial time in $\log p$ and $q$.
The tool we use is a new variant of the Adleman-Manders-Miller probabilistic algorithm for
taking $q$-th roots, which outputs a unique
solution to the input equations and runs in expected polynomial time in
$\log p$ and $q$.
\item given a multi-variate polynomial $P\neq 0$, find a unique (with high probability) $\vec{a}$ such that
$P(\vec{a})\neq0$. Alternatively you may think of this as producing a unique polynomial time
verifiable certificate of inequality of polynomials.
\end{itemize}

More generally, we show a necessary and sufficient condition for the existence of
a Bellagio Algorithm for relation $R$: $R$ has a Bellagio algorithm if and only
if it is deterministically reducible to some decision problem in BPP.

In this paper we introduce a new type of probabilistic search algorithm, which we call the
{\it Bellagio} algorithm: a probabilistic algorithm which is guaranteed to run in expected polynomial time,
and to produce a correct and {\it unique} solution with high probability.
We argue the applicability of such algorithms for
the problems of verifying delegated computation in a distributed setting, and for generating
cryptographic public-parameters and keys in distributed settings.
We exhibit several examples of Bellagio algorithms for problems
for which no deterministic polynomial time algorithms are known.
In particular,we show such algorithms for:
\begin{itemize}
\item finding a unique generator
for \Z\ when $p$ is a prime of the form $kq+1$ for $q$ is prime and $k = \polylog(p)$.
The algorithm runs in expected polynomial in $\log p$ time.
\item finding a
unique $q$'th non-residues of \Z\ for any prime divisor $q$ of $p-1$,
extending Lenstra's \cite{L} algorithm for finding unique quadratic non-residue of \Z.
The algorithm runs in expected polynomial time in $\log p$ and $q$.
The tool we use is a new variant of the Adleman-Manders-Miller probabilistic algorithm for
taking $q$-th roots, which outputs a unique
solution to the input equations and runs in expected polynomial time in
$\log p$ and $q$.
\item given a multi-variate polynomial $P\neq 0$, find a unique (with high probability) $\vec{a}$ such that
$P(\vec{a})\neq0$. Alternatively you may think of this as producing a unique polynomial time
verifiable certificate of inequality of polynomials.
\end{itemize}

More generally, we show a necessary and sufficient condition for the existence of
a Bellagio Algorithm for relation $R$: $R$ has a Bellagio algorithm if and only
if it is deterministically reducible to some decision problem in BPP.