Ultimately I'm trying to define all the steps necessary to go from this toy quartic polynomial modulus:
$$x^4 + 21x^3 + 5x^2 + 7x + 1 \equiv 0 \mod 23$$
to:
$$x = 18, 19$$
One of the recommended first steps is to use the polynomial version of Euclid's Algorithm like this:
$$\gcd(x^4 + 21 x^3 + 5 x^2 + 7 x + 1,x^{23}-x)$$
From what I've gathered, the solution is: $$x^2+9x+20$$
For this question, can someone guide me through the steps involved in reaching $x^2+9x+20$? Bonus points if steps to $x = -5, -4$ were provided. 🙂
I've read many wiki pages, watched several youtube videos, and countless stackexchange posts on the matter and I'm more confused now than when I started. In each example, it seems the initial setup introduces forms of polynomials I have no idea how they're are obtained.
Part of my confusion stems from the fact that polynomial long division is often mentioned as one of the steps and illustrations indicate that when using my $x^{23}-x$, that one of the steps is a polynomial with an x of all powers from 19 to 0.
For example:
$$x^{19} + 2 x^{18} + 22 x^{17} + 4 x^{16} + 21 x^{15} + 4 x^{14} + 14 x^{13} + 18 x^{12} + 9 x^{11} + 10 x^{10} + 19 x^{9} + 22 x^{8} + 8 x^{7} + 16 x^{6} + 3 x^{5} + 9 x^{4} + 21 x^{3} + 6 x^{2} + 2 x + 2$$
I need to use a solution that does not do this because my real problem involves a modulus n of $115792089237316195423570985008687907852837564279074904382605163141518161494337$ and I couldn't even write this out in this universe's lifetime.
This post suggests that Square-and-multiply can be used to quickly find this answer. I am familiar with the Square-and-multiply technique using numbers, but am all thumbs where polynomials are involved.
Any clarity would be helpful here. Steps would be great. Thanks!
By the way, the modulus here is prime so the Chinese remainder theorem and Hensel lifting aren't necessary.
Update
Here is what I'm actually trying to solve. Hope it sheds some light into the right approach with my toy example.
$$\gcd(x^4 + 104904789243076764769272258331008861968773673797810778195683332912883890030960x^3 + 0x^2 + 7476413576101162797801345879216150799700321200725070869821865316357935848858x + 115422971207940030049746909572711733051107198341303901253516904650890299203952, x^{115792089237316195423570985008687907852837564279074904382605163141518161494337} – x)$$
Best Answer
Ok. One more annotated run of Cantor-Zassenhaus :-)
Let $f(x)$ be your quartic. The first step is, indeed, to calculate $\gcd(f(x),x^{23}-x)$. The reason for this is that modulo the prime $p=23$ $$ x^{23}-x=\prod_{j=0}^{22}(x-j). $$ By uniqueness of factorization in the polynomial ring $\Bbb{F}_p[x]$ it follows that $$ g(x):=\gcd(f(x),x^{23}-x)=\prod_{a\in\Bbb{F}_{23},f(a)=0}(x-a). $$ Implying that any zero $a\in\Bbb{F}_p$ of $f(x)$ is a simple zero of $g(x)$. Further implying that the degree of $g(x)$ tells us the number of distinct zeros in the prime field.
The first step in Euclid's algorithm calls for the remainder of $x^{23}-x$ modulo $f(x)$. This I recommend (at least in the not toy example!) you to calculate with square-and-multiply. First, by repeated squaring $$ \begin{aligned} x&\equiv x\pmod{f},\\ x^2&\equiv x^2\pmod{f},\\ x^4&\equiv x^4-f(x)=2 x^3+18 x^2+16 x+22\pmod{f},\\ x^8&\equiv (2 x^3+18 x^2+16 x+22)^2\equiv 4 x^3+6 x^2+10 x+2\pmod{f},\\ x^{16}&\equiv(4 x^3 + 6 x^2 + 10 x + 2)^2\equiv (15 + 14 x + 17 x^2 + 16 x^3)\pmod{f}. \end{aligned} $$ In the last couple steps we had to do a banal squaring, BUT it was a calculation involving low degree polynomials only (here cubics). This is a theme in all of Cantor-Zassenhaus (and also Berlekamp): arithmetic operations involving low degree polynomials are cheap (in terms of complexity).
Next I want to calculate the remainder of $x^{23}$ modulo $f$. All I need to observe is that $$23=16+4+2+1$$ from writing $p=23$ in binary. Therefore $$ x^{23}\equiv x^{16}\cdot x^4\cdot x^2\cdot x\pmod {f}. $$ But we already calculated the remainders of those factors on the right. They are all cubics at worst, so it is cheap to calculate their product modulo $f$. Do it two factors at a time! Then you never need to deal with polynomials of degrees higher than six, and reducing those modulo $f$ is cheap. The result of this calculation is that $$ x^{23}-x\equiv 21 + 6 x + 16 x^2\pmod {f}. $$ The next step in Euclid's algorithm calls us to calculate the remainder of $f$ modulo that first remainder $r_1(x)=21 + 6 x + 16 x^2$. This is, again, a calculation involving low degree polynomials only. Today is our lucky day, because it turns out the next remainder is zero. In other words, $r_1(x)$ is a factor of $f$. Normally we would have gotten another remainder $r_2(x)$, then calculated the remainder of $r_1(x)$ modulo $r_2(x)$ etc. But that's all "cheap".
For easier manipulation I normalize and make $r_1(x)$ monic by dividing with its leading coefficient: $$ g(x)=\gcd(f(x),x^{23}-x)=16^{-1}r_1(x)=13r_1(x)=x^2+9x+20. $$ An important observation here is that if we use a larger prime $p$ the only step where we had to deal with high degree polynomials was the first one of calculating the remainder of $x^p-x$ modulo $f(x)$. And that could be carried out with $\log_2p$ repeated squarings (each "cheap" individually) and the at most $\log_2p$ multiplications involving low degree polynomials. So to summarize: calculating the remainder of $x^p-x$ modulo $f$ takes at worst $2\log_2p$ cheap operations. This is not a bad complexity at all!
But we are not done. Imagining that in place of $23$ we have a huge prime, we cannot find the roots of $g(x)$ either by testing the candidates in sequence. We need to factor $g(x)$ further. But, we already know that $g(x)$ factors into linear terms because $g(x)$ is a factor of $x^p-x$.
The idea in Cantor-Zassenhaus factorization is to use proper "random" factors of $x^{23}-x$ in its place. A common scheme is to use the set $Q_p$ of quadratic residues modulo $p$. From Euler's formula we know that all the elements of $Q_p$ are zeros of the polynomial $x^{(p-1)/2}-1$. In our toy case, of $x^{11}-1$. As above, $$ \gcd(g(x),x^{11}-1)=\prod_{a\in Q_p,g(a)=0}(x-a). $$ So here $x^{11}-1$ (really $x^{(p-1)/2}-1$) can be a ridiculously high degree polynomial. But, because it is a binomial, its remainder modulo $g(x)$ can be calculated by square-and-multiply "cheaply". And then we are, again, left with low degree polynomials making the rest of Euclid easy. I spare you the details and simply tell that $$ \gcd(x^2+9x+20,x^{11}-1)=x+5. $$ The following things need to be noted: