Input:a polynomial fE Fx]of degree d. Output:f三0？ Deterministic algorithm (polynomial interpolation): pick arbitrary distinct., check if f(x)=0 for all0≤i≤d; Fundamental Theorem of Algebra. Any non-zero d-degree polynomial fE Fx]has at most d roots. Randomized algorithm(fingerprinting): pick a uniform random re S; let S Fbe arbitrary check if f(r)=0; (whose size to be fixed later)Input: a polynomial of degree . Output: ? f ∈ 𝔽[x] d f ≡ 0 • Deterministic algorithm (polynomial interpolation): pick arbitrary distinct ; check if for all ; x0, x1, …, xd ∈ 𝔽 f(xi ) = 0 0 ≤ i ≤ d • Randomized algorithm (fingerprinting): pick a uniform random ; check if ; r f(r) = 0 ∈ S let be arbitrary (whose size to be fixed later) S ⊆ 𝔽 Fundamental Theorem of Algebra. Any non-zero d-degree polynomial f ∈ 𝔽[x] has at most d roots