So I'm trying to understand algorithm 2.40 (arbitrary reduction polynomials) from the Guide to Elliptic Curve Cryptography and have some questions.
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?
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?
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?
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$?
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?