Ask Your Question

Factoring modulo prime ideal

asked 2019-03-17 12:47:14 +0200

Matti gravatar image

updated 2019-04-18 20:49:53 +0200

slelievre gravatar image

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 flag offensive close merge delete

2 Answers

Sort by » oldest newest most voted

answered 2019-03-17 23:29:43 +0200

rburing gravatar image

updated 2019-03-18 00:02:26 +0200

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)
edit flag offensive delete link more

answered 2019-03-19 00:22:13 +0200

dan_fulea gravatar image

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


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.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools


Asked: 2019-03-17 12:42:53 +0200

Seen: 417 times

Last updated: Apr 18 '19