3

So we have $$p(x)=x^{12}+x^5+x+1$$ and I thought okay, the only possible rational roots will be $\pm 1$ for all polynomials $p$, but for this one I tried -1 and found it is a root. So, after polynomial division:

$$p(x)=(x+1)q(x)$$ where the degree of $q$ is one less than $p$. Now, looking at $q$, I noticed the signs were plus 5 odd minus 3 even. So I thought that $\pm 1$ would never work since the numbers are not balanced we can't have a root.

And yet my friend told me that $x^4+1$ apparently divides $q$. What would be a good way one would figure that out with pen and paper? Do we need to calculate $q$ specifically or can we possibly see it quicker just from looking at $p$?

Snared
  • 865

4 Answers4

3

As @Arthur suggested, if in doubt use polynomial division. This amounts to $$\begin{array}{llll} (x^{12} + x^5 + x + 1) &\div & (x^4+1) & = x^8 - x^4 + x + 1\\ -(x^{12}+x^8)\\ \hline -x^8 + x^5 + x + 1\\ -(-x^8 - x^4)\\ \hline x^5 + x^4 + x + 1\\ -(x^5 + x)\\ \hline x^4 + 1\\ -(x^4 + 1)\\ \hline 0 \end{array}$$ Note that you may always try @Jyrki Lahtonen's nice trick, since if $p \mid f$ then $p \mid (f+g) \iff p \mid g$. In this specific instance it is quite clear that $(x^4+1) \mid (x^5+x)$, so you only need to check, whether $(x^4 + 1) \mid (x^{12}+1)$. With the substitution $z=x^4$ this amounts to checking $(z+1) \mid (z^3+1)$, which is the same as asking whether $-1$ is a root of $z^3+1$ (which it obviously is).

Jonas Linssen
  • 11,016
  • $(x^4+1)(x^8-x^4+x+1)=x^{12}-x^8+x^5+x^4+x^8-x^4+x+1=x^{12}+x^5+x+1$ indeed, is there an algorithmic version of this to factorize any polynomial without a prior guess? – James Apr 13 '23 at 12:54
  • I did not quess $x^8-x^4+x-1$, it is the result of long division in the polynomial ring $Q[x]$... It is basically the same algorithm you use to find out, whether one integer number divides another... – Jonas Linssen Apr 13 '23 at 13:00
  • what if we don't know the divisor candidate $x^4+1$, then there are infinitely many divisors (different coefficients and powers) to test case by case? – James Apr 13 '23 at 13:03
  • 1
    Ah I misunderstood your question. I am unaware of any general factorization algorithm. For polynomials over a finite field, you may use the sieve of Erastothenes in combination with polynomial division. – Jonas Linssen Apr 13 '23 at 13:21
  • 1
    @James Make a substitution $t = x^4$. We get $t^3+tx+x+1 = (t^3+1)+x(t+1) = (t+1)(t^2-t+1)+x(t+1) = (t+1)(t^2-t+x+1) = (x^4+1)(x^8 - x^4+x+1)$ – D S Apr 13 '23 at 17:31
  • 2
    @James, there are algorithms for testing polynomials for irreducibility, and for factoring the ones that factor, and there is active research into finding improvements. It's all a bit difficult to explain in a short space and at an introductory level. A little websearch for polynomial factorization or for polynomial irreducibility testing might get you started on what's out there. – Gerry Myerson Apr 13 '23 at 23:27
  • @GerryMyerson I wonder suppose we take 4 polynomial keys of order 1000 (or higher), $P_1, P_2, P_3, P_4$, then publish the product $Q = P_1P_2P_3P_4$. We then give $P_1$ to Alice, $P_2$ to Bob, $P_3$ to Charlie, and leave $P_4$ secret as the true key to the cryptext. For sufficiently intractable polynomial orders, does this make for a shared key where only 3 of them together can factorize $Q$ completely? – James Apr 14 '23 at 02:41
  • 1
    I'm no expert on this, James, but it seems to me it's no different asking about polynomial keys than asking about numerical keys. More to the point, the comment section of one question is not such a good place to ask another question – it's better to post it as a new question. – Gerry Myerson Apr 14 '23 at 12:49
1

Simple Computation Of The Quotient

Noticing the applicability of a few fairly well-known identities, we can compute the quotient.

Since $u^3+1=(u+1)\left(u^2-u+1\right)$, setting $u=x^4$, we get $x^{12}+1=\left(x^4+1\right)\left(x^8-x^4+1\right)$.

Furthermore, $x^5+x=x\left(x^4+1\right)$.

Therefore, $$ x^{12}+x^5+x+1=\left(x^4+1\right)\left(x^8-x^4+x+1\right) $$

Scaffold Division $$ \require{enclose} \begin{array}{l} \phantom{x^4+1\ \ }x^8\ \ -x^4+x\phantom{5}+1\\[-4pt] x^4+1\enclose{longdiv}{x^{12}\phantom{{}+x^8}+x^5\phantom{{}+x^5}+x+1}\\[-4pt] \phantom{x^4+1\ \ }\underline{x^{12}+x^8}\\[-2pt] \phantom{x^4+1\ \ x^{12}}-x^8+x^5\phantom{{}+x^5}+x+1\\[-4pt] \phantom{x^4+1\ \ x^{12}}\underline{{}-x^8\phantom{{}+x^5\!}-x^4}\\[-2pt] \phantom{x^4+1\ \ x^{12}-x^8+{}\!}x^5+x^4+x+1\\[-4pt] \phantom{x^4+1\ \ x^{12}-x^8+{}\!}\underline{x^5\phantom{{}+x^4}+x}\\[-2pt] \phantom{x^4+1\ \ x^{12}-x^8+x^5+{}\!\!}x^4\phantom{{}+x}+1\\[-4pt] \phantom{x^4+1\ \ x^{12}-x^8+x^5+{}\!\!}\underline{x^4\phantom{{}+x}+1}\\ \end{array} $$

robjohn
  • 345,667
1

Another way

$$x^4+1=0 \implies x_k=e^{i\frac{k\pi}4}\; k=0,1,2,3$$

and

$$p(x_k)= e^{i3k\pi}+e^{i\frac{5k\pi}4}+e^{i\frac{k\pi}4}+1=-1+e^{i\frac{k\pi}4}\left(e^{ik\pi}+1\right)+1=0$$

user
  • 154,566
1

$p(x)=x^4+1\,$ has no multiple roots because $\,\gcd(p, p')=1\,$ and $\,x^4+1 = 0 \iff x^ 4 = -1\,$, then $\,q(x)=x^{12}+x^5+x+1 = (x^4)^3 + (x^4)\cdot x + x + 1 = -1 -x + x + 1 = 0\,$ so it follows that $\,p(x) \mid q(x)\,$.

dxiv
  • 76,497
  • 1
    (+1) I just realized that after fixing my first argument, it was the same as yours, so I removed it. – robjohn Apr 16 '23 at 13:44