# Modular Reduction of polynomials in GF(2^m)

I am having trouble understanding the algorithm implementation in the hardware of the reduction process over Galois fields of $$F_{2^{163}}$$ In the following process, it looks like we are calculating the $$zc(z)$$ value from 2m-2 downto m which the first half of $$c(z)$$

• but I am not getting to understand what is $$r(z)$$ and how it is obtained?

• $$r(z)$$ shouldn't be fixed as $$Z^m$$ and if it s a polynomial what is its value and what is W?

• and how is the process of $$z^k * r(z)$$ viewed as in hardware is it only left shift by 1 for each k and an and gate with $$r(z)$$?

I don't know if this can help you, but did you know if in Binary Arithmetic, you have: $f(z)=z^m+r(z)$; then $z^m =f(z)+r(z)$. NB: The addition here represents the bitwise XOR, that you can easily represent in hardware by appropriate gates. Then Let's continue by examining the reduction algorithm you show us: $c(z)=c_{2.m-2}.z^{2.m-2}+c_{2.m-1}.z^{2.m-1}+\cdots+c_{m}.z^{m}+c_{m-1}.z^{m-1}+\cdots+c_1.z+c_0$ We factorize by $z^m$; then, we obtain: $c(z)=(c_{2.m-2}.z^{m-2}+c_{2.m-1}.z^{m-1}+\cdots+c_{m}).z^{m}+c_{m-1}.z^{m-1}+\cdots+c_1.z+c_0$ And replacing $z^m=f(z)+r(z)$ and performing the reduction mod f(z): the remaining is: $c(z)=(c_{2.m-2}.z^{m-2}+c_{2.m-1}.z^{m-1}+\cdots+c_{m}).r(z)+c_{m-1}.z^{m-1}+\cdots+c_1.z+c_0$ Which can be computed, with the precomputed table!
Another interpretation of $r(z)$ from $z^m =1.f(z)+r(z)$ shows that $r(z)$ is the remainder of the division of $z^m$ by $f(z)$ while the quotient is the constant polynomial 1.
• @user3368764: Regarding my previous answer $C.z^m$ is equivalent mod f(z) to $C.r(z)$. If you're planning to implement a GF(2^163)-multiplier, then f(z) is a irreduccible polynomial. Then for performing Scalar multiplication over GF(2^163), the pre-computation table must be calculated Once at the set up of the system. Generally in binary arithmetic f(z) is a trimomial, then performing addition are very fast, with appreciable gain in memory ressources. Commented Dec 24, 2014 at 23:00
• @user3368764: You don't need to perform the division $\lfloor (i-m)/W \rfloor$, as you know the exact values of the loop limit. All you have to do is the translate to new bound limit. The division of this is truncated to the floor integer. For recommandation on ECC on Binary field, a large documentation exist over the web. Despite the simplicity of Arithmetic, ECC on prime field are prefered in industrial application. Commented Dec 24, 2014 at 23:50