ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 18 Apr 2017 11:45:53 +0200How to find the multiplicative order of an element in a quotient ring over finite field ?https://ask.sagemath.org/question/37287/how-to-find-the-multiplicative-order-of-an-element-in-a-quotient-ring-over-finite-field/ Exampe,I am trying to find the order of (x+1) in F2[x]/<x^n+1>, For which x^n+1 factored into irreducible polynomial by cyclotomic polynomial. Please can any one help me. How to compute order for each factor for all n stars from 1-300:Thu, 13 Apr 2017 21:18:48 +0200https://ask.sagemath.org/question/37287/how-to-find-the-multiplicative-order-of-an-element-in-a-quotient-ring-over-finite-field/Answer by nd for <p>Exampe,I am trying to find the order of (x+1) in F2[x]/<x^n+1>, For which x^n+1 factored into irreducible polynomial by cyclotomic polynomial. Please can any one help me. How to compute order for each factor for all n stars from 1-300:</p>
https://ask.sagemath.org/question/37287/how-to-find-the-multiplicative-order-of-an-element-in-a-quotient-ring-over-finite-field/?answer=37294#post-id-37294You have (X+1)^2k = X^2k + 1 + 2(...) so ( X+1 )^2k = 0 mod ( X^2k +1 , 2 )
In other words (X+1)^n is nilpotent in any ring F2[X]/(X^n+1) when n is even, so it remains to concentrate on odd values of n
try something like this (N rather small...)
for i in range(2,10):
A=R.quo(x^(2*i+1)+1);j=2
while A((x+1)^j)<>A(x+1):
j=j+1Fri, 14 Apr 2017 10:44:00 +0200https://ask.sagemath.org/question/37287/how-to-find-the-multiplicative-order-of-an-element-in-a-quotient-ring-over-finite-field/?answer=37294#post-id-37294Answer by dan_fulea for <p>Exampe,I am trying to find the order of (x+1) in F2[x]/<x^n+1>, For which x^n+1 factored into irreducible polynomial by cyclotomic polynomial. Please can any one help me. How to compute order for each factor for all n stars from 1-300:</p>
https://ask.sagemath.org/question/37287/how-to-find-the-multiplicative-order-of-an-element-in-a-quotient-ring-over-finite-field/?answer=37321#post-id-37321I suppose, we need "something like" a "multiplicative order" of $(x+1)$ in the ring.
A first problem is that $(x+1)$ is not a unit. It is a zero divisor, since $X^n+1=X^n-1 = (X-1)(\dots)=(X+1)(\dots)$
in the polynomial ring in $X$ over the field with two elements. So we cannot use the word "order" (in the multiplicative sense).
(Well, getting the additive order could not be the problem, so we try to give a sense to the question for the
multiplication as considered operation...)
OK, let us define a "pseudomultiplicative order" by passing to an isomorphic ring and ignoring the factors where $(x+1)$ becomes
nilpotent.
Just as an example, to fix the framework, let us take $n=99$.
Then
$$ {\mathbb F}_2[X] /(X^{99}+1)\ \cong\ ({\mathbb F}_2[X]/(X+1))\times ({\mathbb F}_2[X]/(X^{98}+\dots+X^2+X+1))\ .
$$
The image of $(x+1)$ in the cartesian product of the right side is $(0,x+1)$, so $(x+1)$ is not a unit.
We will tacitly ignore the first cartesian factor and ask for the order of $(x+1)$ in
$$
{\mathbb F}_2[X]/(X^{98}+\dots+X^2+X+1)
$$
where $x$ is now the image of $X$ in the above quotient. This ring still splits corresponding to the factorization of the
moded out polynomial:
n = 99
F = GF(2)
A.<X> = PolynomialRing( F )
MOD = A( (X^n + 1) / (X+1) )
R.<x> = A.quotient( MOD )
print "(X^%s+1) / (X+1) has the following factors over GF(2) :" % n
for f, _ in MOD.factor():
print f
And we get
(X^99+1) / (X+1) has the following factors over GF(2) :
X^2 + X + 1
X^6 + X^3 + 1
X^10 + X^7 + X^5 + X^3 + 1
X^10 + X^9 + X^5 + X + 1
X^10 + X^9 + X^8 + X^7 + X^6 + X^5 + X^4 + X^3 + X^2 + X + 1
X^30 + X^21 + X^15 + X^9 + 1
X^30 + X^27 + X^15 + X^3 + 1
Each factor is irreducible.
We use the structure theorem (Chinese Reminder Theorem, CRT) $R/(fg)\cong (R/f)\times (R/g)$.
(The map in one direction is canonical. The CRT
insures it is a bijection.) We have more than two factors, so we need
the inducitively extended version of CTR. So in our case, the ring ${\mathbb F}_2[X]/(X^{98}+\dots+X^2+X+1)$ is isomorphic
to the cross product of the following fields:
${\mathbb F}_2[X]/(X^2 + X + 1)$, and
${\mathbb F}_2[X]/(X^6 + X^3 + 1 )$, and
${\mathbb F}_2[X]/(X^{10} + X^7 + X^5 + X^3 + 1 )$, and
${\mathbb F}_2[X]/(X^{10} + X^9 + X^5 + X + 1 )$, and
${\mathbb F}_2[X]/(X^{10} + X^9 + X^8 + X^7 + X^6 + X^5 + X^4 + X^3 + X^2 + X + 1 )$, and
${\mathbb F}_2[X]/(X^{30} + X^{21} + X^{15} + X^9 + 1 )$, and
${\mathbb F}_2[X]/(X^{30} + X^{27} + X^{15} + X^3 + 1 )$.
The order of these fields are respectively $2^2$, $2^6$, $2^{10}$ three times, and $2^{30}$ twice.
The order of the respective subjacent (cyclic) multiplicative group of nonzero elements is
$2^2-1$, $2^6-1$, $2^{10}-1$ three times, and $2^{30}-1$ twice.
The element $(x+1)$ has mapped images in all these fields. So it has an order dividing the lcm of all these numbers.
Which is of course $M = 2^{30}-1$ in our case. It is still possible, that the order drops by a divisor of this number.
Let us see first that $(x+1)^M$ is the one.
n = 99
F = GF(2)
A.<X> = PolynomialRing( F )
MOD = A( (X^n + 1) / (X+1) )
R.<x> = A.quotient( MOD )
M = lcm( [ 2^f.degree() - 1 for f, _ in MOD.factor() ] )
print "(x+1)^%s = %s" % ( M, (x+1)^M )
And we get:
(x+1)^1073741823 = 1
(Unfortunately we cannot obtain simply (x+1).multiplicative_order() although the method is there...
Not no my machine with sage in version 'SageMath version 7.6, Release Date: 2017-03-25'. An error occurs.)
Let us get the order now:
divisors = M.divisors()
divisors . sort() # i suspect they were already...
for d in divisors:
if (x+1)^d == R(1):
print "(x+1)^%s = %s" % ( d, (x+1)^d )
break
And we get:
(x+1)^3243933 = 1
Alternatively, we can start with the polynomial $f = (X^n+1)/(X+1)$, factor it,
for each prime=irreducible factor $g$ of it we consider the field ${\mathbb F}_2[X]/(g)$, then the image of
$x$, which is $X$ modulo $f$, is $y$ -- say -- , which is $X$ modulo $g$.
We get the multiplicative order of $y+1$ in this field.
Then we consider
the lcm of all these orders, when $g$ runs in the list of all factors of $f$. The code for this is:
n = 99
F = GF(2)
A.<X> = PolynomialRing( F )
MOD = A( (X^n + 1) / (X+1) )
ords = [] # this is a list of orders, and we will append...
for g, gmultiplicity in MOD.factor():
R.<y> = GF( 2**g.degree(), modulus=g )
ords.append( (y+1).multiplicative_order() )
print "order(x+1) = lcm of %s = %s" % ( str(ords), lcm(ords) )
... getting:
order(x+1) = lcm of [3, 63, 1023, 1023, 341, 3243933, 3243933] = 3243933
So for a general $n$ the following function does the job in the sense above.
(For an EVEN $n$ i will extract the right power of two to be used for making the program still work.)
def getOrder( n, verbose=False ):
"""get the order of (x+1) in the ring
R[ X ] / f
where f = (X^n+1) / (X+1)^(right power)
"""
powerof2 = Qp(2)(n).valuation()
q = 2 ** powerof2
F = GF(2)
A.<X> = F[]
MOD = A( (X^n + 1) / (X+1)^q )
ords = [] # this is a list of orders, and we will append...
for g, gmultiplicity in MOD.factor():
R.<y> = GF( 2**g.degree(), modulus=g )
ords.append( (y+1).multiplicative_order() )
M = lcm( ords )
if verbose:
print "n = %s :: order(x+1) = lcm of %s = %s" % ( n, str(ords), M.factor() )
return M
Above, we fix an $n$. We write than $n= k\cdot q$, where $q=2^r$ is the maximal power of two dividing $n$.
Then
$$ X^n+1 = (X^k+1)^q=(X+1)^q\cdot (X^{k-1}+\dots+1)^q\ . $$
And the last second factor does not have the root $1$, since $k$ is odd and we have $k$ terms,
all of them evaluating to one when setting $X=1$.
For $n$ among $124, 125, 126, 127, 128, 129$ we get the following orders:
for n in [ 124 .. 129 ]:
getOrder( n, verbose=True );
And we obtain:
n = 124 :: order(x+1) = lcm of [31, 31, 31, 31, 31, 31] = 31
31
n = 125 :: order(x+1) = lcm of [15, 25575, 140737488355327875] = 3 * 5^3 * 11 * 31 * 251 * 601 * 1801 * 4051
140737488355327875
n = 126 :: order(x+1) = lcm of [3, 7, 7, 21, 63, 63, 9, 63, 63, 63, 21, 63] = 3^2 * 7
63
n = 127 :: order(x+1) = lcm of [127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127, 127] = 127
127
n = 128 :: order(x+1) = lcm of [] = 1
1
n = 129 :: order(x+1) = lcm of [3, 16383, 16383, 5461, 16383, 5461, 16383, 5461, 16383, 16383] = 3 * 43 * 127
16383
The posted question is answered by `[ getOrder(n) for n in [1..300] ]` and takes its seconds.Tue, 18 Apr 2017 11:45:53 +0200https://ask.sagemath.org/question/37287/how-to-find-the-multiplicative-order-of-an-element-in-a-quotient-ring-over-finite-field/?answer=37321#post-id-37321