Input:a polynomial f eF]of degree d Output:f≡O? simple deterministic algorithm: check whether fx)=0 for all x{1,2,...,d+1) Fundamental Theorem of Algebra: A degree d polynomial has at most d roots. Randomized Algorithm pick a uniform random rES; S∈F check whether fr)=0;simple deterministic algorithm: check whether f(x)=0 for all x ￾ {1, 2,...,d + 1} A degree d polynomial has at most d roots. Fundamental Theorem of Algebra: Randomized Algorithm pick a uniform random r ; check whether f(r) = 0 ; ∈S S ￾ F Input: a polynomial of degree d Output: f ￾ F[x] f ￾ 0?