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

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

b = a

m(mod n);

for (i = 1, k) do

if ((b 6= 1) and (b 6= 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 6= 1) then

return f alse;

else

return true;

end if

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

n, n and 2n, respectively.

Implement the following 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 f alse;

end if