Say I have a polynomial over $Q$. Let it be given in the form of arithmetic circuit family ${C_n}$. The randomised poly time algorithm evaluates the polynomial at a random point. What if the number of bits required for the intermediate calculations is too high i.e How can we guarantee that the evaluation does not require more than polynomial bits (polynomial in the size of the circuit) ?
2
-
$\begingroup$ Please define the question more precisely. What field are you working over? $\mathbb{Z}/p\mathbb{Z}$? $\mathbb{Q}$? What research have you done? This is covered in standard resources on polynomial identity testing. $\endgroup$– D.W. ♦Commented Feb 21, 2015 at 7:00
-
$\begingroup$ I saw a few resources. In all of those, there was this assumption that the polynomial can be evaluated at any given point effeciently. But still, you are right. I should have done more research. $\endgroup$– GaganpreetCommented Feb 21, 2015 at 8:14
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
If you're working over $\mathbb{Z}/p\mathbb{Z}$, you don't have to do anything: the intermediate results can't get larger than $p$.
If you're working over $\mathbb{Z}$, the standard trick is to pick a random $k$-bit prime $p$ and then reduce everything modulo $p$, so you are effectively working over $\mathbb{Z}/p\mathbb{Z}$. One can show that the probability of getting a wrong answer using this method is exponentially small in $k$ (using the prime number theorem).
If you're working over $\mathbb{Q}$, you can reduce this to working over $\mathbb{Z}$ by clearing all fractions.
