How to find the co-efficients of a function within Zp[x]?

Question

I am a newbie in Finite Field arithmetic and while trying to implement an Elliptic Curve Cryptography based ABE scheme in a programming language, I am unable to understand how to implement function fields.

I am given a function definition within a finite field of $p(i.e. Z_p[x])$ where $p$ is some large prime number. How do I find the co-efficient of $x^k$ in the expansion of $f(x)$?

Function definition: $$f(x)=\prod_{i=1}^3 (x+H(i))^i$$ where, H(k) is a one-way hash function giving a large output.

Q1. Since the function is defined in $Z_p[x]$, should all the co-efficient be first calculated using elementary algebra and then taken modulus with $p$?

Q2. If we want to calculate the value of $f(\alpha)$, where $\alpha$ is some constant, can we do it using the final function polynomial of the previous step and substituting all x's with $\alpha$ and then taking a modulus $p$ again?

Answer 1

One thing you can always do in situations like this is "defer the reductions to the end". By this, I mean do all of your calculations in $\mathbb{Z}[x]$, and then at the end "perform reductions until you no longer can", where the two kinds of reductions you do in $\mathbb{Z}/p\mathbb{Z}[x]$ are:

1. Modular reductions (of coefficients): $a\mapsto a\bmod p$
2. Reductions (of variables) according to Fermat's little theorem (if working mod $n$ for a composite number, instead use Euler's theorem): $x^k\mapsto x^{k\bmod \varphi(p)}\bmod p = x^{k\bmod (p-1)}$

As kelalaka points out, you can first expand $f(x)$ as a degree 6 polynomial. As $p$ is large compared to the degree (unless by "large" you mean something like 5), you will need no reductions of the second type, so can solely reduce the coefficients of $f(x)$ mod $p$.

If you have to do these computations on the fly this is not the most efficient thing to do (as the initial computation of $f(x)$ can potentially have a very large representation compared to the reduced version, and you may have to do arithmetic with very large numbers in computing this), but it can be useful both conceptually, and fine when you need to pre-process a polynomial (as you do now).

Essentially, arithmetic with polynomials $\bmod n$ can be split into (familiar) integer polynomial arithmetic, followed by applications of the above two reduction rules.

Answer 2

How do I find the co-efficient of $x^k$ in the expansion of $f(x)$?

$$f(x)=\prod_{i=1}^3 (x+H(i))^i$$

Using Wolfram Alpha try online

$$f(x) = (H(1) + x) (H(2) + x)^2 (H(3) + x)^3$$ and an see the expanded form there.

This is a one-time job. If the $H$ is defined can be shortened, too. The $H(i)$ values should be reduced into $\pmod p$ before multiplications

$$f(x) = (H(1) \bmod p+ x) (H(2) \bmod p + x)^2 (H(3) \bmod p+ x)^3$$

The $x^k$ over there. With SageMath Symbolic Coefficients you can do it, too. (try here)

var('x,a,b,c')
p = (x+a)*(x+b)^2*(x+c)^3

print(p.collect(x)) #Collect the coefficients into a group.

coef = 5
print( "coeff x^", coef, " = ", p.coefficient(x^coef))

Q1. Since, the function is defined in $Z_p[x]$, should all the co-efficient be first calculated using elementary algebra and then taken modulus with p?

No, not necessary, you can only need to calculate the ones that contribute $x^k$.

Q2. If we want to calculate the value of $f(\alpha)$, where $\alpha$ is some constant, can we do it using the final function polynomial of the previous step and substituting all x's with $\alpha$ and then taking a modulus $p$ again?

First, apply the value of the $\alpha$, then all will be numbers, and calculate each by taking modulo in each step to reduce the multiplication time, This is common like a modular repeated squaring algorithm.