2
$\begingroup$

I am having trouble finding info on how to factor polynomials in ring of integers modulo powerful number.

For example: $x^2 - 1$ in $\textbf Z_{8}$.

I know by tinkering around that $(x - 1)(x + 1)$ and $(x - 3)(x + 3)$ are the factorizations, but I don't know how to factor polynomials in ring of integers modulo powerful number in general, which would have helped me solve this particular one much more quickly.

$\endgroup$
  • $\begingroup$ You probably want to learn about Hensel lifting. It says that under certain circumstances you can "lift" a factorization modulo $p$ to a factorization modulo $p^2$, then modulo $p^3$ et cetera. You example polynomial is a notorious example, of when things don't work out so well. The reason is that the derivative of your polynomial $f'(x)=2x$ evaluated at the modulo $2$ zero $x=1$ will be divisible by $2$. There are ways to work around this, but you need to modify the details of the lifting process a little. $\endgroup$ – Jyrki Lahtonen Jul 10 '16 at 18:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.