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