Ask Your Question
1

Collect irreducible polynomials

asked 2016-03-06 16:42:43 -0500

Simple gravatar image

updated 2016-03-07 14:57:19 -0500

tmonteil gravatar image

I am trying to collect irreducible polynomials from a monic polynomial like x^n-1 in a field.

For example, n = 13 and the field is F_{3}, the monic polynomial is x^13-1. So far, I found I can use _factor()_ to get

FF.<a>=GF(3)

x = PolynomialRing(FF,"x").gen()

factor(x^13-1)

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

But I want to make each of them into a list, then from that list to get higher degree irreducible polynomials, such as (x+2)(x^3+2*x+2),(x+2)(x^3+2*x+2)(x^3+2*x^2+2*x+2) and so forth.

can someone give me a hint or suggestion to do that? Thanks. I am not an English speaker, hope people can understand what I say.

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
0

answered 2016-03-07 15:15:06 -0500

tmonteil gravatar image

To get the list of factors, you can simply do:

sage: L = list(factor(x^13-1))
sage: L
[(x + 2, 1),
 (x^3 + 2*x + 2, 1),
 (x^3 + x^2 + 2, 1),
 (x^3 + x^2 + x + 2, 1),
 (x^3 + 2*x^2 + 2*x + 2, 1)]

Here, each factor has multiplicity 1, so you can forget about the second information as follows:

sage: M = [l[0] for l in L]
sage: M
[x + 2, x^3 + 2*x + 2, x^3 + x^2 + 2, x^3 + x^2 + x + 2, x^3 + 2*x^2 + 2*x + 2]

Then you can make the iterated products as follows:

sage: [prod(M[:i]) for i in range(1,len(M)+1)]
[x + 2,
 x^4 + 2*x^3 + 2*x^2 + 1,
 x^7 + x^5 + x^4 + 2*x^3 + 2*x^2 + 2,
 x^10 + x^9 + 2*x^8 + x^7 + x^6 + x^5 + 2*x^3 + 2*x + 1,
 x^13 + 2]

Now, if you have some non-trivial multiplicities, and you want to take them into account, you can define M as follows to repeat each factor the number of times you need:

sage: L = factor(x^8 + x^7 + x^6 + x^2 + x + 1)
sage: L
(x + 2)^2 * (x^2 + 1)^3

sage: M = []
sage: for f,m in L:
....:     M += [f]*m
sage: M
[x + 2, x + 2, x^2 + 1, x^2 + 1, x^2 + 1]

Then as before:

sage: [prod(M[:i]) for i in range(1,len(M)+1)]
[x + 2,
 x^2 + x + 1,
 x^4 + x^3 + 2*x^2 + x + 1,
 x^6 + x^5 + 2*x^3 + x + 1,
 x^8 + x^7 + x^6 + x^2 + x + 1]
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

1 follower

Stats

Asked: 2016-03-06 16:42:43 -0500

Seen: 81 times

Last updated: Mar 07 '16