2
$\begingroup$

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)$?

Modulus Reduction

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ oh ok ! thank you .. and regarding W as word length so if i have a polynomial of 163 than my W is 163 bits ? and in the loop j=(i-m)/W how is the division by W done ? and how did we get zm=zm+r(z) ? I am confused a bit on the second part where we had the C.Zm and then it changed to C.r(z) $\endgroup$
    – user3368764
    Commented Dec 24, 2014 at 21:44
  • $\begingroup$ I am also looking on reading materials regarding ECC on binary fields and some on block cipher algorithm and text to point encoding on binary fields what do you recommend ? thank you $\endgroup$
    – user3368764
    Commented Dec 24, 2014 at 22:02
  • $\begingroup$ @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. $\endgroup$
    – Robert NACIRI
    Commented Dec 24, 2014 at 23:00
  • $\begingroup$ @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. $\endgroup$
    – Robert NACIRI
    Commented Dec 24, 2014 at 23:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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