Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

The given code could not be fully understood. (What is "output [0]"?)

However, the following should be enough.

sage: F = GF(2) sage: R.<x> = F[] sage: factor( x^5-1 ) (x + 1) * (x^4 + x^3 + x^2 + x + 1)

So the ring obtained by taking $R$ modulo $(x^5-1)^2$ is isomorphic to $$ \mathbb F_2[x]/(x+1)^2\ \times \ \mathbb F_2[x]/(x^4 + x^3 + x^2 + x+1)^2\ .$$ (Chinese R.T.)

A an element in the cartesian product of rings is a unit iff each cartesian component of the element is a unit.

Let $P$ be irreducible in $R$. An element in $$ \mathbb F_2[x]/P^2$$ is a unit, iff its image in the field $ \mathbb F_2[x]/P$ is a unit, i.e. is not zero. (Since a polynomial $1+rP$ has the inverse $1-rP$ in the ring $R/(P^2)$.)

Some sample sage code:

sage: F = GF(2)
sage: R.<x> = F[]
sage: S.<u> = R.quotient( [ (x^5-1)^2 ] )
sage: u.is_unit()
True
sage: 1/u
u^9
sage: HF = Hom( S, F )
sage: f = HF( [F(1)] )
sage: f(u)
1
sage: F25.<v> = GF(2**4, modulus=x^4 + x^3 + x^2 + x + 1 ) 
sage: HF25 = Hom( S, F25 )
sage: g = HF25( [v] )
sage: g(u)
v
sage: # let us test if u^3+u+1 is a unit in S
sage: y = u^3 + u + 1
sage: f(y)
1
sage: f(y).is_unit()
True
sage: g(y)
v^3 + v + 1
sage: g(y).is_unit()
True
sage: y.is_unit()
True
sage: 1/y
u^9 + u^6 + u^4 + u^3 + u^2
sage: # let us compute the multiplicative order of y
sage: f(y).multiplicative_order()
1
sage: g(y).multiplicative_order()
15
sage: y^15
u^8 + u^7 + u^6 + u^5 + u^3 + u^2 + u
sage: y^30
1
sage: y^10
u^8 + u^2 + 1
sage: y^6
u^8

So the multiplicative order of $y=u^3+u+1$ was computed by mapping it to the two fields, compute there the multiplicative orders, take the lcm of them. (Well, the one field is simple, order is one for "each" unit.) Then compute the $y$--power of order this lcm. If it is one, this is the order. Else take the square. In our case, $y^{30}=1$ in $S$. But no divisor of $30$ "works instead", so the order is $30$.

The given code could not be fully understood. (What is "output [0]"?)

However, the following way to view the things should be enough.

enough to proceed in the given case, and in a similar more general one.

We start with:

sage: F = GF(2)
sage: R.<x> = F[]
sage: factor( x^5-1 ) 
(x + 1) * (x^4 + x^3 + x^2 + x + 1)

1)

So the ring obtained by taking $R$ modulo $(x^5-1)^2$ is isomorphic to $$ \mathbb F_2[x]/(x+1)^2\ \times \ \mathbb F_2[x]/(x^4 + x^3 + x^2 + x+1)^2\ .$$ (Chinese R.T.)

A an element in the cartesian product of rings is a unit iff each cartesian component of the element is a unit.

Let $P$ be irreducible in $R$. An element in $$ \mathbb F_2[x]/P^2$$ is a unit, iff its image in the field $ \mathbb F_2[x]/P$ is a unit, i.e. is not zero. (Since a polynomial $1+rP$ has the inverse $1-rP$ in the ring $R/(P^2)$.)

Some sample sage code:

sage: F = GF(2)
sage: R.<x> = F[]
sage: S.<u> = R.quotient( [ (x^5-1)^2 ] )
sage: u.is_unit()
True
sage: 1/u
u^9
sage: HF = Hom( S, F )
sage: f = HF( [F(1)] )
sage: f(u)
1
sage: F25.<v> = GF(2**4, modulus=x^4 + x^3 + x^2 + x + 1 ) 
sage: HF25 = Hom( S, F25 )
sage: g = HF25( [v] )
sage: g(u)
v
sage: # let us test if u^3+u+1 is a unit in S
sage: y = u^3 + u + 1
sage: f(y)
1
sage: f(y).is_unit()
True
sage: g(y)
v^3 + v + 1
sage: g(y).is_unit()
True
sage: y.is_unit()
True
sage: 1/y
u^9 + u^6 + u^4 + u^3 + u^2
sage: # let us compute the multiplicative order of y
sage: f(y).multiplicative_order()
1
sage: g(y).multiplicative_order()
15
sage: y^15
u^8 + u^7 + u^6 + u^5 + u^3 + u^2 + u
sage: y^30
1
sage: y^10
u^8 + u^2 + 1
sage: y^6
u^8

So the multiplicative order of $y=u^3+u+1$ was computed by mapping it to the two fields, compute there the multiplicative orders, take the lcm of them. (Well, the one field is simple, order is one for "each" unit.) Then compute the $y$--power of order this lcm. If it is one, this is the order. Else take the square. In our case, $y^{30}=1$ in $S$. But no divisor of $30$ "works instead", so the order is $30$.

$30$.