1 | initial version |
I tried to reproduce the code in a simple situation. This is the only way to debug. Some comments are added, as an advice to have a clean code in a clean framework, so that a clean debug can be started.
dimension = 5 # degree of polynomials
modulus = 3 # ** NOT A ** modulus, but the characteristic of the ring R below
For short: The quotient is taken, but the rest is needed. There are problems with the insignificant zeros in T( rc ).list() .
Note: i had some problems to submit the longer answer. Trying this short one instead.
2 | No.2 Revision |
I tried to reproduce the code in a simple situation. This is the only way to debug. Some comments are added, as an advice to have a clean code in a clean framework, so that a clean debug can be started.
dimension = 5 # degree of polynomials
modulus = 3 # ** NOT A ** modulus, but the characteristic of the ring R below
For short: The quotient is taken, but the rest is needed. There are problems with the insignificant zeros in T( rc ).list() .
Note: i had some problems to submit the longer answer. Trying this short one instead.
dimension = 5 # degree of polynomials
modulus = 3 # ** NOT A ** modulus, but the characteristic of the ring R below
# ring = x^dimension + 1
ring = [1, 0, 0, 0, 0, 1] # bad name for a list representing a pol
# Quotient polynomial ring
R.<X> = PolynomialRing( GF(modulus) ) # Gaussian field of integers
Y.<x> = R.quotient( X^(dimension) + 1 ) # ** NOT A * Cyclotomic field
def division(N, D):
"""WHAT ARE N, D?
Please always insert a comment and a test code.
For instance:
sage: division( [1,0,0,0,0,0,0], [1,0] ) --> Traceback
IndexError: list assignment index out of range
sage: division( [1,0,0,0,0,0,0], [1,0,1] )
([0], [1]) # (?)
sage: division( [1,0,0,0,0,0,0,1], [1,0,1] )
([0, 1, 0, 1, 0, 1, 0], [1, 1])
Is the questioned "division" (?) wanted like that? than i suppose we divide
1 + 0*X + ... (only zeros) by 1 + 0*X + 1*X^2.
"""
dD = degree(D)
dN = degree(N)
if dD < 0: raise ZeroDivisionError
if dN >= dD:
q = [0] * dN
while dN >= dD:
d = [0] * (dN - dD) + D
mult = q[dN - dD] = N[-1] / d[-1]
d = [coeff * mult for coeff in d]
N = [abs(coeffN - coeffd) for coeffN, coeffd in izip(N, d)]
dN = degree(N)
r = N
else:
q = [0]
r = N
return (q, r)
3 | No.3 Revision |
I tried to reproduce the code in a simple situation. This is the only way to debug. Some comments are added, as an advice to have a clean code in a clean framework, so that a clean debug can be started.
For short: The quotient is taken, but the rest is needed. There are problems with the insignificant zeros in T( rc ).list() .
Note: i had some problems to submit the longer answer. Trying this short one instead.
dimension = 5 # degree of polynomials
modulus = 3 # ** NOT A ** modulus, but the characteristic of the ring R below
# ring = x^dimension + 1
ring = [1, 0, 0, 0, 0, 1] # bad name for a list representing a pol
# Quotient polynomial ring
R.<X> = PolynomialRing( GF(modulus) ) # Gaussian field of integers
Y.<x> = R.quotient( X^(dimension) + 1 ) # ** NOT A * Cyclotomic field
def division(N, D):
"""WHAT ARE N, D?
Please always insert a comment and a test code.
For instance:
sage: division( [1,0,0,0,0,0,0], [1,0] ) --> Traceback
IndexError: list assignment index out of range
sage: division( [1,0,0,0,0,0,0], [1,0,1] )
([0], [1]) # (?)
sage: division( [1,0,0,0,0,0,0,1], [1,0,1] )
([0, 1, 0, 1, 0, 1, 0], [1, 1])
Is the questioned "division" (?) wanted like that? than i suppose we divide
1 + 0*X + ... (only zeros) by 1 + 0*X + 1*X^2.
"""
dD = degree(D)
dN = degree(N)
if dD < 0: raise ZeroDivisionError
if dN >= dD:
q = [0] * dN
while dN >= dD:
d = [0] * (dN - dD) + D
mult = q[dN - dD] = N[-1] / d[-1]
d = [coeff * mult for coeff in d]
N = [abs(coeffN - coeffd) for coeffN, coeffd in izip(N, d)]
dN = degree(N)
r = N
else:
q = [0]
r = N
return (q, r)
def degree(poly):
while poly and poly[-1] == 0:
poly.pop() # normalize
return len(poly) - 1
def ring_correct( poly, irreduciblePoly, modulus ):
"""The irreduciblePoly is not irreducible (and not a poly) in the call.
"""
poly = division( poly, irreduciblePoly )[1] # ??? Do you want the quotient or the rest???
poly = map( lambda xx: xx % modulus, poly )
# x % modulus... why this complication?
# Why not x in GF(3) directly,
# never use the same x again, although the namespace should be safe...
return poly
T.<t> = PolynomialRing(ZZ, 'x')
# a = gen()
for a in ( [ 1,0,1,2,1,1 ] ,
[ 1,0,0,2,0,2 ] ,
[ 1,0,0,2,0,2 ] ,
[ 2,1,0,2,0,2 ] ,
[ 2,1,0,2,0,1 ] ,
[ 2,1,0,2,0,1 ] ,
[ 2,1,1,1,1,1 ] ,
[ 2,1,0,1,2,1 ] ):
Ya = Y(a)
rc = ring_correct( a, ring, modulus ) # hard to guess what it codes
Trc = T( rc ) # but we make a polynomial out of it
print ( "a = %s :: %5s ::\n\tYa = %s :: Ya.list() = %s\n\tTrc = %s :: Trc.list() = %s\n"
% ( a, Ya.list() == Trc.list(), Ya, Ya.list(), Trc, Trc.list() ) )
4 | No.4 Revision |
I tried to reproduce the code in a simple situation. This is the only way to debug. Some comments are added, as an advice to have a clean code in a clean framework, so that a clean debug can be started.
For short: The quotient is taken, but the rest is needed. There are problems with the insignificant zeros in T( rc ).list() .
Note: (Note: i had some problems to submit the longer answer. Trying this short one instead.to partially send instead.)
dimension = 5 # degree of polynomials
modulus = 3 # ** NOT A ** modulus, but the characteristic of the ring R below
# ring = x^dimension + 1
ring = [1, 0, 0, 0, 0, 1] # bad name for a list representing a pol
# Quotient polynomial ring
R.<X> = PolynomialRing( GF(modulus) ) # Gaussian field of integers
Y.<x> = R.quotient( X^(dimension) + 1 ) # ** NOT A * Cyclotomic field
def division(N, D):
"""WHAT ARE N, D?
Please always insert a comment and a test code.
For instance:
sage: division( [1,0,0,0,0,0,0], [1,0] ) --> Traceback
IndexError: list assignment index out of range
sage: division( [1,0,0,0,0,0,0], [1,0,1] )
([0], [1]) # (?)
sage: division( [1,0,0,0,0,0,0,1], [1,0,1] )
([0, 1, 0, 1, 0, 1, 0], [1, 1])
Is the questioned "division" (?) wanted like that? than i suppose we divide
1 + 0*X + ... (only zeros) by 1 + 0*X + 1*X^2.
"""
dD = degree(D)
dN = degree(N)
if dD < 0: raise ZeroDivisionError
if dN >= dD:
q = [0] * dN
while dN >= dD:
d = [0] * (dN - dD) + D
mult = q[dN - dD] = N[-1] / d[-1]
d = [coeff * mult for coeff in d]
N = [abs(coeffN - coeffd) for coeffN, coeffd in izip(N, d)]
dN = degree(N)
r = N
else:
q = [0]
r = N
return (q, r)
def degree(poly):
while poly and poly[-1] == 0:
poly.pop() # normalize
return len(poly) - 1
def ring_correct( poly, irreduciblePoly, modulus ):
"""The irreduciblePoly is not irreducible (and not a poly) in the call.
"""
poly = division( poly, irreduciblePoly )[1] # ??? Do you want the quotient or the rest???
poly = map( lambda xx: xx % modulus, poly )
# x % modulus... why this complication?
# Why not x in GF(3) directly,
# never use the same x again, although the namespace should be safe...
return poly
T.<t> = PolynomialRing(ZZ, 'x')
# a = gen()
for a in ( [ 1,0,1,2,1,1 ] ,
[ 1,0,0,2,0,2 ] ,
[ 1,0,0,2,0,2 ] ,
[ 2,1,0,2,0,2 ] ,
[ 2,1,0,2,0,1 ] ,
[ 2,1,0,2,0,1 ] ,
[ 2,1,1,1,1,1 ] ,
[ 2,1,0,1,2,1 ] ):
Ya = Y(a)
rc = ring_correct( a, ring, modulus ) # hard to guess what it codes
Trc = T( rc ) # but we make a polynomial out of it
print ( "a = %s :: %5s ::\n\tYa = %s :: Ya.list() = %s\n\tTrc = %s :: Trc.list() = %s\n"
% ( a, Ya.list() == Trc.list(), Ya, Ya.list(), Trc, Trc.list() ) )
There was one "important" error above, i replaced [ 0 ] with [ 1 ], since we want the rest, not the quotient. And we get in this deterministic context also the difference between Ya.list() and Trc.list() :
Ya = x^4 + 2*x^3 + x^2 and Ya.list() = [0, 0, 1, 2, 1]
Trc = t^4 + 2*t^3 + t^2 and Trc.list() = [0, 0, 1, 2, 1]
# but
Ya = 2*x^3 + 2 and Ya.list() = [2, 0, 0, 2, 0]
Trc = 2*t^3 + 1 and Trc.list() = [1, 0, 0, 2]