Re: [sage-support] Question about Patterson Algorithm Implementation
This is definitely not a bug. The definition of the _add_ method absolutely demands that both inputs have exactly the same parent. In the above instance, the left hand input (=1) has parent ZZ, and the right hand input (=SR(2)) has parent the symbolic ring. Yeah, I know that-- it's the violation of that assumption which ultimately crashed the OP's code, after all. I guess I've inherited the bias from Python that users shouldn't be able to segfault the interpreter from pure Python code. Anything Cythonic probably falls into the Sage equivalent of the ctypes exception class, and I guess you can get the same crash with any non-typechecking cpdef'd object, but it still feels wrong. Meh. Doug -- To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
Re: [sage-support] Question about Patterson Algorithm Implementation
Hi thanks for your answers,
I used _inverter_, _mul_, _add_ etc, because apparently
the implementation work fine but only apparently,
i think that the essencial problem is with _invert_ method,
but now I used inverse_mod , but I dont
where are the error, I implemented Berlekamp Algorithm too, from [Ict2011],
its inside worksheet,
this work fine, but Patterson Algorithm no,
please help me with this implementation
'''
ALGORITHM:
The following two algorithms are in [Ict2011]
REFERENCES:
.. [Ict2011] How SAGE helps to implement Goppa Codes and McEliece PKCSs
URL :
http://www.google.com/url?sa=tsource=webcd=2ved=0CCUQFjABurl=http%3A%2F%2Fwww.weblearn.hs-bremen.de%2Frisse%2Fpapers%2FICIT11%2FRisse526ICIT11.pdfei=Q-yCTpK5C82cgQfj3803usg=AFQjCNGEZ7SuMf1WKPrdkxvJMfiSaSqO1wsig2=3RM25hfPNHCveQvdjTn4Iw
'''
def encode(u):
return u*G_Goppa;
#this is the Berlekamp
def decode(y,m,N,H_gRS):
tt = var('z')
s = H_gRS*y.transpose();
if s==matrix(Phi,H_gRS.nrows(),1):
return y;
b = PR([s[_,0] for _ in range(s.nrows())]);
#
bigN = m;
sigma = vector(PolynomialRing(Phi,tt),bigN+2);
omega = vector(PolynomialRing(Phi,tt),bigN+2);
delta = vector(PolynomialRing(Phi,tt),bigN+2);
sigma[-1+1] = PR(0);
sigma[0+1] = PR(1);
flag = 2*bigN; # exponent flags rational 1/z
omega[-1+1] = z**flag;
omega[0+1] = PR(0);
# init mu and delta
mu = -1; delta[-1+1] = 1;
for i in range(bigN):
delta[i+1] = (sigma[i+1]*b).coeffs()[i];
sigma[i+1+1] =
sigma[i+1](z)-z**(i-mu)*(delta[i+1]/delta[mu+1])*sigma[mu+1](z);
if (omega[mu+1].degree()==flag):
omega[i+1+1] =
omega[i+1](z)-(delta[i+1]/delta[mu+1])*z**(i-mu-1);
else:
omega[i+1+1]
=omega[i+1](z)-z**(i-mu)*(delta[i+1]/delta[mu+1])*omega[mu+1](z);
ord = max(sigma[i+1].degree(),1+omega[i+1].degree());
if (delta[i+1]0)and(2*ord=i):
mu = i;
ELP = sigma[bigN+1]; # ErrorLocatorPolynomial
n = G_Goppa.nrows();
ee = vector(F,[0 for _ in range(n)]);
for i in range(N):
if (ELP(x**i)==Phi(0)): # an error occured
print 'error position',N-i
return 0;
def split(p):
# split polynomial p over F into even part po
# and odd part p1 such that p(z) = p2 (z) + z p2 (z)
Phi = p.parent()
p0 = Phi([sqrt(c) for c in p.list()[0::2]]);
p1 = Phi([sqrt(c) for c in p.list()[1::2]]);
return (p0,p1);
m = 4
F.x = GF(2)
Phi.x = GF(2^m);
PR = PolynomialRing(Phi,'z');
print 'PR is',PR;
N = 2^m - 1;
codelocators = [x^i for i in range(N)]
print(codelocators)
X = PolynomialRing(Phi,repr('z')).gen();
g = X^2+X+x^3; # goppa polynomial
print 'goppa polinomial',g
if g.is_irreducible():
print 'g(z) =',g,'is irreducible';
for i in range(N):
if g(codelocators[i])==Phi(0):
print 'alarm: g(alpha_'+str(i)+')=0';
H_gRS = matrix([[codelocators[j]^(i) for j in range(N)] for i in
range(m)]);
H_gRS = H_gRS*diagonal_matrix([ 1/g(codelocators[i]) for i in range(N)]);
print H_gRS
H_Goppa = matrix(F,m*H_gRS.nrows(),H_gRS.ncols());
for i in range(H_gRS.nrows()):
for j in range(H_gRS.ncols()):
be = bin(eval(H_gRS[i,j].int_repr()))[2:];
be = '0'*(m-len(be))+be; be = list(be);
H_Goppa[m*i:m*(i+1),j]=vector(map(int,be));
Krnl = H_Goppa.right_kernel();
G_Goppa = Krnl.basis_matrix();
print H_Goppa
k = G_Goppa.nrows()
u = vector(F,[randint(0,1) for _ in range(k)]);
c = encode(u);
e = vector(F,H_gRS.ncols()); # e = zero vector
e[3]=1
y = vector(F,H_gRS.ncols());
y = c + e
print 'berlekamp algorithm'
decode(y,m,N,H_gRS)
print 'patterson algorithm'
#adicionando error
s = H_gRS*y.transpose();
sP = PR([s[_,0] for _ in range(s.nrows())]);
print 'g=',g
g0g1 = split(g);
w = g0g1[0]*(((g0g1[1]).inverse_mod(g)))
print 'w=',w
T0T1 = split(sP.inverse_mod(g) + X);
R = T0T1[0]+(w)*(T0T1[1])
print 'R',R
(d1,u,v) = xgcd(1,R); # where d = gcd(1,R) = 1
a = g*u; b = g*v;
sigma = (a^2+X*(b^2));
print sigma.roots()
2011/9/28 D. S. McNeil dsm...@gmail.com
This is definitely not a bug. The definition of the _add_ method
absolutely demands that both inputs have exactly the same parent. In
the above instance, the left hand input (=1) has parent ZZ, and the
right hand input (=SR(2)) has parent the symbolic ring.
Yeah, I know that-- it's the violation of that assumption which
ultimately crashed the OP's code, after all.
I guess I've inherited the bias from Python that users shouldn't be
able to segfault the interpreter from pure Python code.
Anything Cythonic probably falls into the Sage equivalent of the
ctypes exception class, and I guess you can get the same crash with
any non-typechecking cpdef'd object, but it still feels wrong.
Meh.
Doug
--
To post to this group, send email to sage-support@googlegroups.com
To unsubscribe from this group, send email to
sage-support+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/sage-support
URL:
Re: [sage-support] Question about Patterson Algorithm Implementation
in the end line
print sigma.roots(),
always give empty vector, here sigma.roots() should nonzero vector
2011/9/28 Juan Grados juan...@gmail.com
Hi thanks for your answers,
I used _inverter_, _mul_, _add_ etc, because apparently
the implementation work fine but only apparently,
i think that the essencial problem is with _invert_ method,
but now I used inverse_mod , but I dont
where are the error, I implemented Berlekamp Algorithm too, from [Ict2011],
its inside worksheet,
this work fine, but Patterson Algorithm no,
please help me with this implementation
'''
ALGORITHM:
The following two algorithms are in [Ict2011]
REFERENCES:
.. [Ict2011] How SAGE helps to implement Goppa Codes and McEliece PKCSs
URL :
http://www.google.com/url?sa=tsource=webcd=2ved=0CCUQFjABurl=http%3A%2F%2Fwww.weblearn.hs-bremen.de%2Frisse%2Fpapers%2FICIT11%2FRisse526ICIT11.pdfei=Q-yCTpK5C82cgQfj3803usg=AFQjCNGEZ7SuMf1WKPrdkxvJMfiSaSqO1wsig2=3RM25hfPNHCveQvdjTn4Iw
'''
def encode(u):
return u*G_Goppa;
#this is the Berlekamp
def decode(y,m,N,H_gRS):
tt = var('z')
s = H_gRS*y.transpose();
if s==matrix(Phi,H_gRS.nrows(),1):
return y;
b = PR([s[_,0] for _ in range(s.nrows())]);
#
bigN = m;
sigma = vector(PolynomialRing(Phi,tt),bigN+2);
omega = vector(PolynomialRing(Phi,tt),bigN+2);
delta = vector(PolynomialRing(Phi,tt),bigN+2);
sigma[-1+1] = PR(0);
sigma[0+1] = PR(1);
flag = 2*bigN; # exponent flags rational 1/z
omega[-1+1] = z**flag;
omega[0+1] = PR(0);
# init mu and delta
mu = -1; delta[-1+1] = 1;
for i in range(bigN):
delta[i+1] = (sigma[i+1]*b).coeffs()[i];
sigma[i+1+1] =
sigma[i+1](z)-z**(i-mu)*(delta[i+1]/delta[mu+1])*sigma[mu+1](z);
if (omega[mu+1].degree()==flag):
omega[i+1+1] =
omega[i+1](z)-(delta[i+1]/delta[mu+1])*z**(i-mu-1);
else:
omega[i+1+1]
=omega[i+1](z)-z**(i-mu)*(delta[i+1]/delta[mu+1])*omega[mu+1](z);
ord = max(sigma[i+1].degree(),1+omega[i+1].degree());
if (delta[i+1]0)and(2*ord=i):
mu = i;
ELP = sigma[bigN+1]; # ErrorLocatorPolynomial
n = G_Goppa.nrows();
ee = vector(F,[0 for _ in range(n)]);
for i in range(N):
if (ELP(x**i)==Phi(0)): # an error occured
print 'error position',N-i
return 0;
def split(p):
# split polynomial p over F into even part po
# and odd part p1 such that p(z) = p2 (z) + z p2 (z)
Phi = p.parent()
p0 = Phi([sqrt(c) for c in p.list()[0::2]]);
p1 = Phi([sqrt(c) for c in p.list()[1::2]]);
return (p0,p1);
m = 4
F.x = GF(2)
Phi.x = GF(2^m);
PR = PolynomialRing(Phi,'z');
print 'PR is',PR;
N = 2^m - 1;
codelocators = [x^i for i in range(N)]
print(codelocators)
X = PolynomialRing(Phi,repr('z')).gen();
g = X^2+X+x^3; # goppa polynomial
print 'goppa polinomial',g
if g.is_irreducible():
print 'g(z) =',g,'is irreducible';
for i in range(N):
if g(codelocators[i])==Phi(0):
print 'alarm: g(alpha_'+str(i)+')=0';
H_gRS = matrix([[codelocators[j]^(i) for j in range(N)] for i in
range(m)]);
H_gRS = H_gRS*diagonal_matrix([ 1/g(codelocators[i]) for i in range(N)]);
print H_gRS
H_Goppa = matrix(F,m*H_gRS.nrows(),H_gRS.ncols());
for i in range(H_gRS.nrows()):
for j in range(H_gRS.ncols()):
be = bin(eval(H_gRS[i,j].int_repr()))[2:];
be = '0'*(m-len(be))+be; be = list(be);
H_Goppa[m*i:m*(i+1),j]=vector(map(int,be));
Krnl = H_Goppa.right_kernel();
G_Goppa = Krnl.basis_matrix();
print H_Goppa
k = G_Goppa.nrows()
u = vector(F,[randint(0,1) for _ in range(k)]);
c = encode(u);
e = vector(F,H_gRS.ncols()); # e = zero vector
e[3]=1
y = vector(F,H_gRS.ncols());
y = c + e
print 'berlekamp algorithm'
decode(y,m,N,H_gRS)
print 'patterson algorithm'
#adicionando error
s = H_gRS*y.transpose();
sP = PR([s[_,0] for _ in range(s.nrows())]);
print 'g=',g
g0g1 = split(g);
w = g0g1[0]*(((g0g1[1]).inverse_mod(g)))
print 'w=',w
T0T1 = split(sP.inverse_mod(g) + X);
R = T0T1[0]+(w)*(T0T1[1])
print 'R',R
(d1,u,v) = xgcd(1,R); # where d = gcd(1,R) = 1
a = g*u; b = g*v;
sigma = (a^2+X*(b^2));
print sigma.roots()
2011/9/28 D. S. McNeil dsm...@gmail.com
This is definitely not a bug. The definition of the _add_ method
absolutely demands that both inputs have exactly the same parent. In
the above instance, the left hand input (=1) has parent ZZ, and the
right hand input (=SR(2)) has parent the symbolic ring.
Yeah, I know that-- it's the violation of that assumption which
ultimately crashed the OP's code, after all.
I guess I've inherited the bias from Python that users shouldn't be
able to segfault the interpreter from pure Python code.
Anything Cythonic probably falls into the Sage equivalent of the
ctypes exception class, and I guess you can get the same crash with
any non-typechecking cpdef'd object, but it still feels wrong.
Re: [sage-support] Question about Patterson Algorithm Implementation
help please!
2011/9/28 Juan Grados juan...@gmail.com
in the end line
print sigma.roots(),
always give empty vector, here sigma.roots() should nonzero vector
2011/9/28 Juan Grados juan...@gmail.com
Hi thanks for your answers,
I used _inverter_, _mul_, _add_ etc, because apparently
the implementation work fine but only apparently,
i think that the essencial problem is with _invert_ method,
but now I used inverse_mod , but I dont
where are the error, I implemented Berlekamp Algorithm too, from
[Ict2011], its inside worksheet,
this work fine, but Patterson Algorithm no,
please help me with this implementation
'''
ALGORITHM:
The following two algorithms are in [Ict2011]
REFERENCES:
.. [Ict2011] How SAGE helps to implement Goppa Codes and McEliece PKCSs
URL :
http://www.google.com/url?sa=tsource=webcd=2ved=0CCUQFjABurl=http%3A%2F%2Fwww.weblearn.hs-bremen.de%2Frisse%2Fpapers%2FICIT11%2FRisse526ICIT11.pdfei=Q-yCTpK5C82cgQfj3803usg=AFQjCNGEZ7SuMf1WKPrdkxvJMfiSaSqO1wsig2=3RM25hfPNHCveQvdjTn4Iw
'''
def encode(u):
return u*G_Goppa;
#this is the Berlekamp
def decode(y,m,N,H_gRS):
tt = var('z')
s = H_gRS*y.transpose();
if s==matrix(Phi,H_gRS.nrows(),1):
return y;
b = PR([s[_,0] for _ in range(s.nrows())]);
#
bigN = m;
sigma = vector(PolynomialRing(Phi,tt),bigN+2);
omega = vector(PolynomialRing(Phi,tt),bigN+2);
delta = vector(PolynomialRing(Phi,tt),bigN+2);
sigma[-1+1] = PR(0);
sigma[0+1] = PR(1);
flag = 2*bigN; # exponent flags rational 1/z
omega[-1+1] = z**flag;
omega[0+1] = PR(0);
# init mu and delta
mu = -1; delta[-1+1] = 1;
for i in range(bigN):
delta[i+1] = (sigma[i+1]*b).coeffs()[i];
sigma[i+1+1] =
sigma[i+1](z)-z**(i-mu)*(delta[i+1]/delta[mu+1])*sigma[mu+1](z);
if (omega[mu+1].degree()==flag):
omega[i+1+1] =
omega[i+1](z)-(delta[i+1]/delta[mu+1])*z**(i-mu-1);
else:
omega[i+1+1]
=omega[i+1](z)-z**(i-mu)*(delta[i+1]/delta[mu+1])*omega[mu+1](z);
ord = max(sigma[i+1].degree(),1+omega[i+1].degree());
if (delta[i+1]0)and(2*ord=i):
mu = i;
ELP = sigma[bigN+1]; # ErrorLocatorPolynomial
n = G_Goppa.nrows();
ee = vector(F,[0 for _ in range(n)]);
for i in range(N):
if (ELP(x**i)==Phi(0)): # an error occured
print 'error position',N-i
return 0;
def split(p):
# split polynomial p over F into even part po
# and odd part p1 such that p(z) = p2 (z) + z p2 (z)
Phi = p.parent()
p0 = Phi([sqrt(c) for c in p.list()[0::2]]);
p1 = Phi([sqrt(c) for c in p.list()[1::2]]);
return (p0,p1);
m = 4
F.x = GF(2)
Phi.x = GF(2^m);
PR = PolynomialRing(Phi,'z');
print 'PR is',PR;
N = 2^m - 1;
codelocators = [x^i for i in range(N)]
print(codelocators)
X = PolynomialRing(Phi,repr('z')).gen();
g = X^2+X+x^3; # goppa polynomial
print 'goppa polinomial',g
if g.is_irreducible():
print 'g(z) =',g,'is irreducible';
for i in range(N):
if g(codelocators[i])==Phi(0):
print 'alarm: g(alpha_'+str(i)+')=0';
H_gRS = matrix([[codelocators[j]^(i) for j in range(N)] for i in
range(m)]);
H_gRS = H_gRS*diagonal_matrix([ 1/g(codelocators[i]) for i in range(N)]);
print H_gRS
H_Goppa = matrix(F,m*H_gRS.nrows(),H_gRS.ncols());
for i in range(H_gRS.nrows()):
for j in range(H_gRS.ncols()):
be = bin(eval(H_gRS[i,j].int_repr()))[2:];
be = '0'*(m-len(be))+be; be = list(be);
H_Goppa[m*i:m*(i+1),j]=vector(map(int,be));
Krnl = H_Goppa.right_kernel();
G_Goppa = Krnl.basis_matrix();
print H_Goppa
k = G_Goppa.nrows()
u = vector(F,[randint(0,1) for _ in range(k)]);
c = encode(u);
e = vector(F,H_gRS.ncols()); # e = zero vector
e[3]=1
y = vector(F,H_gRS.ncols());
y = c + e
print 'berlekamp algorithm'
decode(y,m,N,H_gRS)
print 'patterson algorithm'
#adicionando error
s = H_gRS*y.transpose();
sP = PR([s[_,0] for _ in range(s.nrows())]);
print 'g=',g
g0g1 = split(g);
w = g0g1[0]*(((g0g1[1]).inverse_mod(g)))
print 'w=',w
T0T1 = split(sP.inverse_mod(g) + X);
R = T0T1[0]+(w)*(T0T1[1])
print 'R',R
(d1,u,v) = xgcd(1,R); # where d = gcd(1,R) = 1
a = g*u; b = g*v;
sigma = (a^2+X*(b^2));
print sigma.roots()
2011/9/28 D. S. McNeil dsm...@gmail.com
This is definitely not a bug. The definition of the _add_ method
absolutely demands that both inputs have exactly the same parent. In
the above instance, the left hand input (=1) has parent ZZ, and the
right hand input (=SR(2)) has parent the symbolic ring.
Yeah, I know that-- it's the violation of that assumption which
ultimately crashed the OP's code, after all.
I guess I've inherited the bias from Python that users shouldn't be
able to segfault the interpreter from pure Python code.
Anything Cythonic probably falls into the Sage equivalent of the
ctypes exception class, and I guess you can get the same crash with
any
Re: [sage-support] Question about Patterson Algorithm Implementation
Hi David,
Yes I understand, but now I think that have a logic problem in algorithm,
but I don't know where ... i copying lines from [Ict2011], ...
2011/9/28 David Joyner wdjoy...@gmail.com
On Wed, Sep 28, 2011 at 5:58 PM, Juan Grados juan...@gmail.com wrote:
help please!
They did seem to solve your problem, didn't they?
Do you not understand the English? Do you simply disagree?
If you don't understand the English, please find someone who can translate.
Did you find another error after fixing the problem they told about?
Please be very clear exactly what it is you are having a problem
understanding in this thread.
2011/9/28 Juan Grados juan...@gmail.com
in the end line
print sigma.roots(),
always give empty vector, here sigma.roots() should nonzero vector
2011/9/28 Juan Grados juan...@gmail.com
Hi thanks for your answers,
I used _inverter_, _mul_, _add_ etc, because apparently
the implementation work fine but only apparently,
i think that the essencial problem is with _invert_ method,
but now I used inverse_mod , but I dont
where are the error, I implemented Berlekamp Algorithm too, from
[Ict2011], its inside worksheet,
this work fine, but Patterson Algorithm no,
please help me with this implementation
'''
ALGORITHM:
The following two algorithms are in [Ict2011]
REFERENCES:
.. [Ict2011] How SAGE helps to implement Goppa Codes and McEliece PKCSs
URL
:
http://www.google.com/url?sa=tsource=webcd=2ved=0CCUQFjABurl=http%3A%2F%2Fwww.weblearn.hs-bremen.de%2Frisse%2Fpapers%2FICIT11%2FRisse526ICIT11.pdfei=Q-yCTpK5C82cgQfj3803usg=AFQjCNGEZ7SuMf1WKPrdkxvJMfiSaSqO1wsig2=3RM25hfPNHCveQvdjTn4Iw
'''
def encode(u):
return u*G_Goppa;
#this is the Berlekamp
def decode(y,m,N,H_gRS):
tt = var('z')
s = H_gRS*y.transpose();
if s==matrix(Phi,H_gRS.nrows(),1):
return y;
b = PR([s[_,0] for _ in range(s.nrows())]);
#
bigN = m;
sigma = vector(PolynomialRing(Phi,tt),bigN+2);
omega = vector(PolynomialRing(Phi,tt),bigN+2);
delta = vector(PolynomialRing(Phi,tt),bigN+2);
sigma[-1+1] = PR(0);
sigma[0+1] = PR(1);
flag = 2*bigN; # exponent flags rational 1/z
omega[-1+1] = z**flag;
omega[0+1] = PR(0);
# init mu and delta
mu = -1; delta[-1+1] = 1;
for i in range(bigN):
delta[i+1] = (sigma[i+1]*b).coeffs()[i];
sigma[i+1+1] =
sigma[i+1](z)-z**(i-mu)*(delta[i+1]/delta[mu+1])*sigma[mu+1](z);
if (omega[mu+1].degree()==flag):
omega[i+1+1] =
omega[i+1](z)-(delta[i+1]/delta[mu+1])*z**(i-mu-1);
else:
omega[i+1+1]
=omega[i+1](z)-z**(i-mu)*(delta[i+1]/delta[mu+1])*omega[mu+1](z);
ord = max(sigma[i+1].degree(),1+omega[i+1].degree());
if (delta[i+1]0)and(2*ord=i):
mu = i;
ELP = sigma[bigN+1]; # ErrorLocatorPolynomial
n = G_Goppa.nrows();
ee = vector(F,[0 for _ in range(n)]);
for i in range(N):
if (ELP(x**i)==Phi(0)): # an error occured
print 'error position',N-i
return 0;
def split(p):
# split polynomial p over F into even part po
# and odd part p1 such that p(z) = p2 (z) + z p2 (z)
Phi = p.parent()
p0 = Phi([sqrt(c) for c in p.list()[0::2]]);
p1 = Phi([sqrt(c) for c in p.list()[1::2]]);
return (p0,p1);
m = 4
F.x = GF(2)
Phi.x = GF(2^m);
PR = PolynomialRing(Phi,'z');
print 'PR is',PR;
N = 2^m - 1;
codelocators = [x^i for i in range(N)]
print(codelocators)
X = PolynomialRing(Phi,repr('z')).gen();
g = X^2+X+x^3; # goppa polynomial
print 'goppa polinomial',g
if g.is_irreducible():
print 'g(z) =',g,'is irreducible';
for i in range(N):
if g(codelocators[i])==Phi(0):
print 'alarm: g(alpha_'+str(i)+')=0';
H_gRS = matrix([[codelocators[j]^(i) for j in range(N)] for i in
range(m)]);
H_gRS = H_gRS*diagonal_matrix([ 1/g(codelocators[i]) for i in
range(N)]);
print H_gRS
H_Goppa = matrix(F,m*H_gRS.nrows(),H_gRS.ncols());
for i in range(H_gRS.nrows()):
for j in range(H_gRS.ncols()):
be = bin(eval(H_gRS[i,j].int_repr()))[2:];
be = '0'*(m-len(be))+be; be = list(be);
H_Goppa[m*i:m*(i+1),j]=vector(map(int,be));
Krnl = H_Goppa.right_kernel();
G_Goppa = Krnl.basis_matrix();
print H_Goppa
k = G_Goppa.nrows()
u = vector(F,[randint(0,1) for _ in range(k)]);
c = encode(u);
e = vector(F,H_gRS.ncols()); # e = zero vector
e[3]=1
y = vector(F,H_gRS.ncols());
y = c + e
print 'berlekamp algorithm'
decode(y,m,N,H_gRS)
print 'patterson algorithm'
#adicionando error
s = H_gRS*y.transpose();
sP = PR([s[_,0] for _ in range(s.nrows())]);
print 'g=',g
g0g1 = split(g);
w = g0g1[0]*(((g0g1[1]).inverse_mod(g)))
print 'w=',w
T0T1 = split(sP.inverse_mod(g) + X);
R = T0T1[0]+(w)*(T0T1[1])
print 'R',R
(d1,u,v) = xgcd(1,R); # where d = gcd(1,R) = 1
a = g*u; b = g*v;
Re: [sage-support] Question about Patterson Algorithm Implementation
I have already sent, but I dont answer ... because I expect please only if
anyelse can help me iff a time ...
2011/9/28 David Joyner wdjoy...@gmail.com
On Wed, Sep 28, 2011 at 6:12 PM, Juan Grados juan...@gmail.com wrote:
Hi David,
Yes I understand, but now I think that have a logic problem in algorithm,
but I don't know where ... i copying lines from [Ict2011], ...
I would just email the author of the paper and ask him.
2011/9/28 David Joyner wdjoy...@gmail.com
On Wed, Sep 28, 2011 at 5:58 PM, Juan Grados juan...@gmail.com wrote:
help please!
They did seem to solve your problem, didn't they?
Do you not understand the English? Do you simply disagree?
If you don't understand the English, please find someone who can
translate.
Did you find another error after fixing the problem they told about?
Please be very clear exactly what it is you are having a problem
understanding in this thread.
2011/9/28 Juan Grados juan...@gmail.com
in the end line
print sigma.roots(),
always give empty vector, here sigma.roots() should nonzero vector
2011/9/28 Juan Grados juan...@gmail.com
Hi thanks for your answers,
I used _inverter_, _mul_, _add_ etc, because apparently
the implementation work fine but only apparently,
i think that the essencial problem is with _invert_ method,
but now I used inverse_mod , but I dont
where are the error, I implemented Berlekamp Algorithm too, from
[Ict2011], its inside worksheet,
this work fine, but Patterson Algorithm no,
please help me with this implementation
'''
ALGORITHM:
The following two algorithms are in [Ict2011]
REFERENCES:
.. [Ict2011] How SAGE helps to implement Goppa Codes and McEliece
PKCSs
URL
:
http://www.google.com/url?sa=tsource=webcd=2ved=0CCUQFjABurl=http%3A%2F%2Fwww.weblearn.hs-bremen.de%2Frisse%2Fpapers%2FICIT11%2FRisse526ICIT11.pdfei=Q-yCTpK5C82cgQfj3803usg=AFQjCNGEZ7SuMf1WKPrdkxvJMfiSaSqO1wsig2=3RM25hfPNHCveQvdjTn4Iw
'''
def encode(u):
return u*G_Goppa;
#this is the Berlekamp
def decode(y,m,N,H_gRS):
tt = var('z')
s = H_gRS*y.transpose();
if s==matrix(Phi,H_gRS.nrows(),1):
return y;
b = PR([s[_,0] for _ in range(s.nrows())]);
#
bigN = m;
sigma = vector(PolynomialRing(Phi,tt),bigN+2);
omega = vector(PolynomialRing(Phi,tt),bigN+2);
delta = vector(PolynomialRing(Phi,tt),bigN+2);
sigma[-1+1] = PR(0);
sigma[0+1] = PR(1);
flag = 2*bigN; # exponent flags rational 1/z
omega[-1+1] = z**flag;
omega[0+1] = PR(0);
# init mu and delta
mu = -1; delta[-1+1] = 1;
for i in range(bigN):
delta[i+1] = (sigma[i+1]*b).coeffs()[i];
sigma[i+1+1] =
sigma[i+1](z)-z**(i-mu)*(delta[i+1]/delta[mu+1])*sigma[mu+1](z);
if (omega[mu+1].degree()==flag):
omega[i+1+1] =
omega[i+1](z)-(delta[i+1]/delta[mu+1])*z**(i-mu-1);
else:
omega[i+1+1]
=omega[i+1](z)-z**(i-mu)*(delta[i+1]/delta[mu+1])*omega[mu+1](z);
ord = max(sigma[i+1].degree(),1+omega[i+1].degree());
if (delta[i+1]0)and(2*ord=i):
mu = i;
ELP = sigma[bigN+1]; # ErrorLocatorPolynomial
n = G_Goppa.nrows();
ee = vector(F,[0 for _ in range(n)]);
for i in range(N):
if (ELP(x**i)==Phi(0)): # an error occured
print 'error position',N-i
return 0;
def split(p):
# split polynomial p over F into even part po
# and odd part p1 such that p(z) = p2 (z) + z p2 (z)
Phi = p.parent()
p0 = Phi([sqrt(c) for c in p.list()[0::2]]);
p1 = Phi([sqrt(c) for c in p.list()[1::2]]);
return (p0,p1);
m = 4
F.x = GF(2)
Phi.x = GF(2^m);
PR = PolynomialRing(Phi,'z');
print 'PR is',PR;
N = 2^m - 1;
codelocators = [x^i for i in range(N)]
print(codelocators)
X = PolynomialRing(Phi,repr('z')).gen();
g = X^2+X+x^3; # goppa polynomial
print 'goppa polinomial',g
if g.is_irreducible():
print 'g(z) =',g,'is irreducible';
for i in range(N):
if g(codelocators[i])==Phi(0):
print 'alarm: g(alpha_'+str(i)+')=0';
H_gRS = matrix([[codelocators[j]^(i) for j in range(N)] for i in
range(m)]);
H_gRS = H_gRS*diagonal_matrix([ 1/g(codelocators[i]) for i in
range(N)]);
print H_gRS
H_Goppa = matrix(F,m*H_gRS.nrows(),H_gRS.ncols());
for i in range(H_gRS.nrows()):
for j in range(H_gRS.ncols()):
be = bin(eval(H_gRS[i,j].int_repr()))[2:];
be = '0'*(m-len(be))+be; be = list(be);
H_Goppa[m*i:m*(i+1),j]=vector(map(int,be));
Krnl = H_Goppa.right_kernel();
G_Goppa = Krnl.basis_matrix();
print H_Goppa
k = G_Goppa.nrows()
u = vector(F,[randint(0,1) for _ in range(k)]);
c = encode(u);
e = vector(F,H_gRS.ncols()); # e = zero vector
e[3]=1
y = vector(F,H_gRS.ncols());
y = c
Re: [sage-support] Question about Patterson Algorithm Implementation
I don't think you should need to call _add_, but this looks like a bug to me:
--
| Sage Version 4.7.1, Release Date: 2011-08-11 |
| Type notebook() for the GUI, and license() for information.|
--
sage: 1+SR(2)
3
sage: 1.__add__(SR(2))
3
sage: 1._add_(SR(2))
Unhandled SIGSEGV: A segmentation fault occurred in Sage.
This probably occurred because a *compiled* component of Sage has a bug
in it and is not properly wrapped with sig_on(), sig_off(). You might
want to run Sage under gdb with 'sage -gdb' to debug this.
Sage will now terminate.
Similarly for _sub_ and _mul_. _div_ gives a slightly different result:
sage: 1._div_(SR(2))
ERROR: An unexpected error occurred while tokenizing input
The following traceback may be corrupted or invalid
The error message is: ('EOF in multi-line statement', (3258, 0))
ERROR: An unexpected error occurred while tokenizing input
The following traceback may be corrupted or invalid
The error message is: ('EOF in multi-line statement', (3244, 0))
---
TypeError Traceback (most recent call last)
/Users/mcneil/ipython console in module()
/Applications/sage/local/lib/python2.6/site-packages/sage/rings/integer.so
in sage.rings.integer.Integer._div_ (sage/rings/integer.c:11866)()
/Applications/sage/local/lib/python2.6/site-packages/sage/rings/integer.so
in sage.rings.integer.Integer._div_ (sage/rings/integer.c:11824)()
/Applications/sage/local/lib/python2.6/site-packages/sage/rings/integer_ring.so
in sage.rings.integer_ring.IntegerRing_class._div
(sage/rings/integer_ring.c:5158)()
TypeError: Argument 'right' has incorrect type (expected
sage.rings.integer.Integer, got sage.symbolic.expression.Expression)
Doug
--
To post to this group, send email to sage-support@googlegroups.com
To unsubscribe from this group, send email to
sage-support+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/sage-support
URL: http://www.sagemath.org
Re: [sage-support] Question about Patterson Algorithm Implementation
On Tue, Sep 27, 2011 at 7:15 PM, D. S. McNeil dsm...@gmail.com wrote:
I don't think you should need to call _add_, but this looks like a bug to me:
--
| Sage Version 4.7.1, Release Date: 2011-08-11 |
| Type notebook() for the GUI, and license() for information. |
--
sage: 1+SR(2)
3
sage: 1.__add__(SR(2))
3
sage: 1._add_(SR(2))
Unhandled SIGSEGV: A segmentation fault occurred in Sage.
This probably occurred because a *compiled* component of Sage has a bug
in it and is not properly wrapped with sig_on(), sig_off(). You might
want to run Sage under gdb with 'sage -gdb' to debug this.
Sage will now terminate.
This is definitely not a bug. The definition of the _add_ method
absolutely demands that both inputs have exactly the same parent. In
the above instance, the left hand input (=1) has parent ZZ, and the
right hand input (=SR(2)) has parent the symbolic ring.
-- William
Similarly for _sub_ and _mul_. _div_ gives a slightly different result:
sage: 1._div_(SR(2))
ERROR: An unexpected error occurred while tokenizing input
The following traceback may be corrupted or invalid
The error message is: ('EOF in multi-line statement', (3258, 0))
ERROR: An unexpected error occurred while tokenizing input
The following traceback may be corrupted or invalid
The error message is: ('EOF in multi-line statement', (3244, 0))
---
TypeError Traceback (most recent call last)
/Users/mcneil/ipython console in module()
/Applications/sage/local/lib/python2.6/site-packages/sage/rings/integer.so
in sage.rings.integer.Integer._div_ (sage/rings/integer.c:11866)()
/Applications/sage/local/lib/python2.6/site-packages/sage/rings/integer.so
in sage.rings.integer.Integer._div_ (sage/rings/integer.c:11824)()
/Applications/sage/local/lib/python2.6/site-packages/sage/rings/integer_ring.so
in sage.rings.integer_ring.IntegerRing_class._div
(sage/rings/integer_ring.c:5158)()
TypeError: Argument 'right' has incorrect type (expected
sage.rings.integer.Integer, got sage.symbolic.expression.Expression)
Doug
--
To post to this group, send email to sage-support@googlegroups.com
To unsubscribe from this group, send email to
sage-support+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/sage-support
URL: http://www.sagemath.org
--
William Stein
Professor of Mathematics
University of Washington
http://wstein.org
--
To post to this group, send email to sage-support@googlegroups.com
To unsubscribe from this group, send email to
sage-support+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/sage-support
URL: http://www.sagemath.org
