# Factoring modulo prime ideal

I would like to factor a polynomial with integer coefficients modulo the prime ideal generated by $1-\sqrt{-2}$ in $O_{K},$ where $K=\mathbb{Q}[\sqrt{-2}].$ How can I do this using Sage?

edit retag close merge delete

Sort by » oldest newest most voted

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

more

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.

more