Polynomial Identity Testing (PIT) Input:two polynomials f,gEF[x]of degree d Output:f=g? d ]of degreed:f()=>aixi for ai∈F i=0 Input:a polynomial fFx]of degree d Output:f≡=O? fis given as black-box
Polynomial Identity Testing (PIT) Input: two polynomials f,g F[x] of degree d Output: f g? Input: a polynomial of degree d Output: f F[x] f 0? f is given as black-box f F[x] f(x) = X d i=0 aixi of degree d : for ai 2 F
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?