Ask Your Question
2

Factoring modulo prime ideal

asked 2019-03-17 06:47:14 -0500

Matti gravatar image

updated 2019-04-18 13:49:53 -0500

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
2

answered 2019-03-17 17:29:43 -0500

rburing gravatar image

updated 2019-03-17 18:02:26 -0500

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

answered 2019-03-18 18:22:13 -0500

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
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.

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

Stats

Asked: 2019-03-17 06:42:53 -0500

Seen: 66 times

Last updated: yesterday