Revision history [back]
 | 1 | initial version |
I 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 its order. 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.
| | 2 | No.2 Revision |
I 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)\ /(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 F}_2[X]/(X^{10} + X^7 + X^5 + X^3 + 1 )$, and
${\mathbb F}_2[X]/(X^10 F}_2[X]/(X^{10} + X^9 + X^5 + X + 1 )$, and
${\mathbb F}_2[X]/(X^10 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 F}_2[X]/(X^{30} + X^{21} + X^{15} + X^9 + 1 )$, and
${\mathbb F}_2[X]/(X^30 + X^27 + X^15 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 its order. 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.
| | 3 | No.3 Revision |
I 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$ $f$, is $y$ -- say -- , which is $X$ modulo $g$.
We get its order. 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.
