ASKSAGE: Sage Q&A Forum - Individual question feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 18 Mar 2019 18:22:13 -0500Factoring modulo prime idealhttps://ask.sagemath.org/question/45803/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?Sun, 17 Mar 2019 06:42:53 -0500https://ask.sagemath.org/question/45803/factoring-modulo-prime-ideal/Answer by rburing for <p>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?</p>
https://ask.sagemath.org/question/45803/factoring-modulo-prime-ideal/?answer=45812#post-id-45812Nonzero 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)
TrueSun, 17 Mar 2019 17:29:43 -0500https://ask.sagemath.org/question/45803/factoring-modulo-prime-ideal/?answer=45812#post-id-45812Answer by dan_fulea for <p>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?</p>
https://ask.sagemath.org/question/45803/factoring-modulo-prime-ideal/?answer=45833#post-id-45833I 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](https://ask.sagemath.org/users/24971/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.
Mon, 18 Mar 2019 18:22:13 -0500https://ask.sagemath.org/question/45803/factoring-modulo-prime-ideal/?answer=45833#post-id-45833