2
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ I have seen some resources which mention about Galois Field $\operatorname{GF}(p^n)$ and how we find irreducible polynomials of degree $n-1$. In my opinion we should take the $mod$ of the co-efficients and then after evaluating $f(\alpha)$, we will again take $mod$, am I moving in the right direction? $\endgroup$
    – RJ_SU
    Oct 24 '20 at 16:11
  • $\begingroup$ Please do not provide guesses or followup questions as answers, you can either comment or include some additional information in the question instead. $\endgroup$
    – Maarten Bodewes
    Oct 24 '20 at 17:57
  • $\begingroup$ I'm not seeing the problem as in $\text{GF}(p^n)$, for there is mention of neither the degree $n$, nor of a polynomial acting as a reduction polynomial (which bounded degree would be $n$). I think we are working in the field of polynomials of unbounded degree, with coefficients in $\text{GF}(p)$ (the integers modulo prime $p$). $\endgroup$
    – fgrieu
    Oct 24 '20 at 18:26
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Suggestion: de-emphasize the expanded form, which makes the answer intimidating. Perhaps, make it a link to Wolfram Alpha or a Try it Online!. [update: we can also collect the terms, as asked, see this better TiO] $\endgroup$
    – fgrieu
    Oct 24 '20 at 17:53
  • $\begingroup$ @fgrieu I did. and SageMath has a nice package, too. $\endgroup$
    – kelalaka
    Oct 24 '20 at 20:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.