questions about modular reduction algorithm over $F_{2^m}$

Question

So I'm trying to understand algorithm 2.40 (arbitrary reduction polynomials) from the Guide to Elliptic Curve Cryptography and have some questions.

1. The very first sentence of this section says this:

   Recall that $f(z) = z^m +r(z)$, where $r(z)$ is a binary polynomial of degree at most $m − 1$

   So let's take sect113r1. $f(x)$ is $x^{113}+x^9+1$. It seems like $z^m$ would be $x^{113}$ and $r(z)$ would be $x^9+1$. Is that a correct assumption?

2. The algorithm uses $c$ and $C$ and I'm wondering if they're the same thing. Like it says this:

   INPUT: A binary polynomial $c(z)$ of degree at most $2m −2$.

   ...and it also says this:

   Add $u_k(z)$ to $C\{j\}$.

   $C\{j\}$ is defined thusly:

   The following notation is used: if $C = (C[n], . . .,C[2],C[1],C[0])$ is an array, then $C\{j\}$ denotes the truncated array $(C[n], . . .,C[ j +1],C[ j ])$.

   The thing is... $C$ is not defined prior to the "Add" line. So it seems to me that either $C$ and $c$ are supposed to be the same thing or $C$ is supposed to be pre-initialized to all 0's?

3. So for the "Add $u_k(z)$ to $C\{j\}$" step... I assume that means to add by doing XOR? What if $u_k(z)$ and $C\{j\}$ are of different sizes? Do we pad both of them with 0's on the right or left side?

4. So let's say $W$ equals 8. That means that the largest value of $u_k(z)$ is going to be $z^7r(z)$, which, assuming my understanding in #1 was correct, would mean that, for sect113r1, that it'd be $x^{16}+x^7$. So we add that (perhaps simply by doing XOR, per question #3) to $C\{j\}$ (which I asked about in question #2). The concern I have is... let's say $C\{j\}$ is 0. At that point the result would be $x^{16}+x^7$, which is bigger than $W$ and I'd kinda expect it to less than $W$. Otherwise it's not really clear to me what that algorithm is supposed to be returning. Like maybe each element could be a digit in a bigint with a limb size equal to $W$?

5. In the last step it says "Return$(C[t−1], . . .,C[1],C[0])$". What is $t$ supposed to be? It's not defined or referenced anywhere else. Maybe it's supposed to be the length of C?

Answer 1

So let's take sect113r1. $f(x)$ is $x^{113}+x^9+1$. It seems like $z^m$ would be $x^{113}$ and $r(z)$ would be $x^9+1$. Is that a correct assumption?

Correct, we have $m = 113$, hence $z^m = z^{113}$ and $r(z) = z^9 + 1$.

The algorithm uses $c$ and $C$ and I'm wondering if they're the same thing.

They are very closely related, $c(z)$ is a univariate polynomial in $z$ (with coefficients in $GF(2)$), and $C$ is the representation of that polynomial using words of size $W$ (in bits). So if we have $c(z) = z^7 + z^3 + z + 1$ and $W = 8$, we would have $C = (C[0]) = (10001011)$. $C$ gives us an unambiguous way of representing $c(z)$.

So for the "Add $u_k(z)$ to $C\{j\}$" step... I assume that means to add by doing XOR? What if $u_k(z)$ and $C\{j\}$ are of different sizes? Do we pad both of them with 0's on the right or left side?

I believe the addition algorithm is specified earlier in that section but yes, if you are representing univariate polynomials as described above then you can XOR the values to get the result of addition (since XOR is addition in $GF(2)$). If you follow the convention that the coefficient of the highest degree term in the polynomial is the MSB in the last word ($C[n]$), then you don't need to zero pad. If you have less words in one polynomial than the other, you can skip addition (since XOR by all 0 is the identity function) and just take those words as is. As an example, with $W = 4$

$$a(z) = z^7 + z^3 + z + 1$$ $$b(z) = z^3 + z^2$$ $$c(z) = a(z) + b(z) = z^7 + 2z^3 + z^2 + z + 1 = z^7 + z^2 + z + 1$$ $$A = (1000, 1011)$$ $$B = (1100)$$ $$C = (1000 (\oplus 0000), 1011 \oplus 1100) = (1000, 0111)$$

So let's say $W$ equals 8...The concern I have is... let's say $C\{j\}$ is 0. At that point the result would be $x^{16}+x7$, which is bigger than $W$ and I'd kinda expect it to less than W.

Why must the result be less than $W$ (bits)? If $W = 8$ then clearly we need more than one $W$ bit word to represent a polynomial with degree 113. There's no reason we can't have intermediate values that are also greater than one word. Again, see my answer above as to how represent a polynomial with multiple words.

In the last step it says "Return($C[t−1],...,C[1],C[0]$)". What is $t$ supposed to be? It's not defined or referenced anywhere else. Maybe it's supposed to be the length of C?

Remember that $C$ represents a polynomial with degree up to 224. But we are reducing by $f(z)$ which is of degree 113, so we don't need all the words of $C$. In the introduction to Section 2.3 "Binary field arithmetic" it states "Let $t = \mathrm{ceiling}(\frac{m}{W})$", hence $t$ is the maximum number of words need to represent an element $\bmod{f(z)}$ where $m$ is the degree of $f(z)$.