Input:a polynomial fE Fx]of degree d. Output:f三0？ pick a uniform random re S; let S Fbe arbitrary check if f(r)=0; (whose size to-be fixed later) |S|=2d iff≡O:always correct ff丰0： Pr[fr）=O]≤ d 1 ISI 2 Fundamental Theorem of Algebra. Any non-zero d-degree polynomial f Fx]has at most d roots.pick a uniform random ; check if ; r f(r) = 0 ∈ S let be arbitrary (whose size to be fixed later) S ⊆ 𝔽 if f ≡ 0: always correct Input: a polynomial of degree . Output: ? f ∈ 𝔽[x] d f ≡ 0 if f ≢ 0: Pr[f(r) = 0] ≤ |S| Fundamental Theorem of Algebra. Any non-zero d-degree polynomial f ∈ 𝔽[x] has at most d roots. d |S| = 2d = 1 2