Factoring modulo prime ideal

savecancel

Nonzero prime ideals in a Dedekind domain – such as $\mathfrak{p} = (1-\sqrt{-2})$ in $O_K$ – are maximal, so the quotient is a field, called the residue field in Sage:

K.<a> = QuadraticField(-2)
OK = K.ring_of_integers()
P = OK.ideal(1-a)
OK_mod_P = P.residue_field()

Then you can factor polynomials over $O_K/\mathfrak{p}$, e.g. as follows:

sage: R.<x> = PolynomialRing(ZZ)
sage: f = x^3 + 5
sage: f_mod_P = f.change_ring(OK_mod_P); f_mod_P
x^3 + 2
sage: f_mod_P.factor()
(x + 2)^3

You can also lift the factorization and double-check the result (e.g. for fun):

sage: S.<y> = PolynomialRing(OK)
sage: factorization_lift = prod(S(g)^e for (g,e) in f_mod_P.factor()); factorization_lift
y^3 + 6*y^2 + 12*y + 8
sage: S(f) - factorization_lift
-6*y^2 - 12*y - 3
sage: S(f) - factorization_lift in S.ideal(P)
True

I would solve the problem first rather in the mathematical world, because the chain of isomorphisms $$\frac{\Bbb Z[\sqrt{-2}] }{(1-\sqrt{-2})} \cong \frac{\Bbb Z[A] /(A^2+2) }{(1-A)} \cong \frac{\Bbb Z[A]}{(A^2+2,\;1-A)} \cong \frac{\Bbb Z[A] /(1-A) }{(A^2+2)} \overset{A\to 1}\cong \frac{\Bbb Z }{(1+2)} \cong \Bbb F_3$$ shows that we have to factorize the "given" polynomial in $\Bbb Z[X]$ or $\Bbb Z[X,Y]$ or ... after passing to $\Bbb F_3[X]$ or $\Bbb F_3[X,Y]$ or ...

Now, starting from a polynomial over $\Bbb Z$ we can quickly pass to $\Bbb F_3$ and factorize, for instance:

R.<X> = PolynomialRing(ZZ)
R3.<x> = PolynomialRing(GF(3))
f = X^5 + 7*X^4 - 6*X^3 + 9*X^2 - 11*X + 12
R3(f)
R3(f).factor()

gives:

x^5 + x^4 + x
x * (x + 2) * (x^3 + 2*x^2 + 2*x + 2)

The good solution doing mot-a-mot the requested job (and which is easy to adapt to similar situation blindly) is detailed above with illustrating examples by rburing. This answer only want to show that things are in a special case sometimes simpler to do as expected, above, sage passes at request via the canonical morphism $\Bbb Z[X]\to \Bbb F_3[x]$ (coercion) from one world to the other.