Given {(x1,y1),...,(xn,yn)}, we can interpolate a polynomial P. Assume polynomial P has some roots including an specific root β.
Consider we change one of yi to y′i. Given {(x1,y1),...,(xi,y′i),..,(xn,yn)} we interpolate a polynomial P′.
Question 1: Would it be possible that P′ has the root β, too?
Question 2: Would it be possible that P′ has the same degree as P and P′ has the root β, too?
Notation: yi is defined as P(xi)=yi
Edit: xi≠0 , xi≠xj, the polynomials, xi's and yi's are defined over finite field Fp for a large prime p.
Answer
Actually if β is not one of your xj's then it's impossible. Indeed, the two polynomials P and P′ have degree n−1 (at most) and take the same value on all xj for j≠i (namely, yj), so if they both vanished at β they would have the same value at n points, and thus they would be equal, which is not the case since they have different values at xi.
Of course, as pointed out in the comments, if β=xj≠xi then P and P′ trivially a common root.
No comments:
Post a Comment