(Monte Carlo)

find k, m ∈ N s. t. n − 1 = 2^k *m, m odd;

choose uniformly a ∈ {2, 3, . . . , n − 2};

b = a^m (mod n);

for (i = 1, k) do

if ((b != 1) and (b != n − 1)) then

return false;

else if (b = n − 1) then

return true;

end if

b = b^2(mod n); // bb mod n

end for

if (b != 1) then

return false;

else

return true;

end if

another

f(X), g(X) and h(X) three polynomials of degrees n, n and 2n.

randomized algorithm for testing polynomial equality (f · g = h)? :

choose uniformly p ∈ {1, 2, . . . , 3n};

if (f(p) · g(p) = h(p)) then

return true;

else

return false;

end if