(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