Calculating some equations

Question

Having these functions:

f(x)= 4(x-1)(x-3)/(0-1)(0-3)
g(x)= 2(x-0)(x-3)/(1-0)(1-3)
h(x)= 3(x-0)(x-1)/(3-0)(3-1)

I want to calculate their sum mod p. For reference, p=7.

However, what interests me mostly is the coefficients of the powers of x from the final result. Will show you what I mean

My steps:

f(x)=4(x-1)(x-3)/3
g(x)=-(x-0)(x-3)
h(x)=(x-0)(x-1)/2

f(x)+g(x)+h(x)=(8(x-1)(x-3)-6(x-0)(x-3)+3(x-0)(x-1))/6
=(8(x^2-4x+3)-6(x^2-3x)+3(x^2-x))/6
=(8x^2-32x+24-6x^2+18x+3x^2-3x)/6
=(5x^2-17x+24)/6

1/6 mod 7=6

So, we get to multiply by 6 instead of dividing the parenthesis, which will be made mod 7, too:

=(5x^2-17x+24)*6
=30x^2-102+144 

This will also be mod 7, but if I can get the coefficients I can do it separately for each of them. The final result will be 2x^2+3x+4

So, what interests me are the coefficients 30, -102 and 144(or 2,3,4, doesn't matter). How can I compute in java to get them from f+g+h, if there is a faster or easier way(I may have done useless steps in my calculations)?

Answer 1

As far as I can see, you are computing Lagrange polynomials.

In the specific case of 3 data points (x_0, y_0), (x_1, y_1), (x_2, y_2) - which in your example are (0, 4), (1, 2), (3, 3), the calculation is quite easy.

f(x) = y_0*l_0(x) = y_0/((x_0-x_1)*(x_0-x_2))*(x^2 + -(x_1+x_2)*x + (x_1*x_2))

The other two polynomials can be computed similarly.

In their sum, you just have to group together the corresponding coefficients, and make the modular arithmetic. (Division can be made with the multiplication of the inverse element, and the inverse element can be easily computed with the help of Fermat's little theorem as a^(p-2) in case of prime modulus.)