# 线性码与密码¶

## 代码¶

Sage可以计算汉明码

sage: C = codes.HammingCode(GF(3), 3)
sage: C
[13, 10] Hamming Code over GF(3)
sage: C.minimum_distance()
3
sage: C.generator_matrix()
[1 0 0 0 0 0 0 0 0 0 1 2 0]
[0 1 0 0 0 0 0 0 0 0 0 1 2]
[0 0 1 0 0 0 0 0 0 0 1 0 2]
[0 0 0 1 0 0 0 0 0 0 1 1 1]
[0 0 0 0 1 0 0 0 0 0 1 1 2]
[0 0 0 0 0 1 0 0 0 0 2 0 2]
[0 0 0 0 0 0 1 0 0 0 1 2 1]
[0 0 0 0 0 0 0 1 0 0 2 1 1]
[0 0 0 0 0 0 0 0 1 0 2 2 0]
[0 0 0 0 0 0 0 0 0 1 0 1 1]


sage: C = codes.GolayCode(GF(3))
sage: C
[12, 6, 6] Extended Golay code over GF(3)
sage: C.minimum_distance()
6
sage: C.generator_matrix()
[1 0 0 0 0 0 2 0 1 2 1 2]
[0 1 0 0 0 0 1 2 2 2 1 0]
[0 0 1 0 0 0 1 1 1 0 1 1]
[0 0 0 1 0 0 1 1 0 2 2 2]
[0 0 0 0 1 0 2 1 2 2 0 1]
[0 0 0 0 0 1 0 2 1 2 2 1]


sage: C = codes.HammingCode(GF(2), 3)
sage: Cperp = C.dual_code()
sage: C; Cperp
[7, 4] Hamming Code over GF(2)
[7, 3] linear code over GF(2)
sage: C.generator_matrix()
[1 0 0 0 0 1 1]
[0 1 0 0 1 0 1]
[0 0 1 0 1 1 0]
[0 0 0 1 1 1 1]
sage: C.parity_check_matrix()
[1 0 1 0 1 0 1]
[0 1 1 0 0 1 1]
[0 0 0 1 1 1 1]
sage: C.dual_code()
[7, 3] linear code over GF(2)
sage: C = codes.HammingCode(GF(4,'a'), 3)
sage: C.dual_code()
[21, 3] linear code over GF(4)


sage: C = codes.HammingCode(GF(2), 3)
sage: MS = MatrixSpace(GF(2),1,7)
sage: F = GF(2); a = F.gen()
sage: v = vector([a,a,F(0),a,a,F(0),a])
sage: c = C.decode_to_code(v, "Syndrome"); c
(1, 1, 0, 1, 0, 0, 1)
sage: c in C
True


sage: C = codes.HammingCode(GF(2), 4)
sage: C
[15, 11] Hamming Code over GF(2)
sage: w = C.weight_distribution(); w
[1, 0, 0, 35, 105, 168, 280, 435, 435, 280, 168, 105, 35, 0, 0, 1]
sage: J = range(len(w))
sage: W = IndexedSequence([ZZ(w[i]) for i in J],J)
sage: P = W.plot_histogram()


Sage还可以通过奇异接口§第二节：agcodes。也可以通过Sage接口使用GUAVA中实现的AG代码 gap_console() . 更多详情请参阅番石榴手册。{GUAVA}

## 密码¶

### LFSRs¶

S、 Golomb{G}给出了一个由三个统计属性组成的一系列数字 $${{\bf a}}=\{{a_n\}}_{{n=1}}^\infty$$$$a_n\in \{{0,1\}}$$ ，应显示为“随机”。定义的自相关 $${{\bf a}}$$ 成为

$C（k）=C（k，{bfa}）=lim{Nrightarrowinfty}frac{1}{N}sum{N=1}^N（-1）^{a{N+a{N+k}}。$

• 余额： $$|\sum_{{n=1}}^P(-1)^{{a_n}}|\leq 1$$ .

• 低自相关：

$C（k）=left{begin{array}{cc}1，&k=0，\epsilon，&knot=0。右结束{array}右。$

（对于满足前两个性质的序列，已知 $$\epsilon=-1/P$$ 必须保持住。）

• 比例运行特性：在每个周期中，有一半的运行具有长度 $$1$$ 四分之一有长度 $$2$$ 等等。移动，有很多次 $$1$$ 就像现在一样 $$0$$ s。

$begin{array}{c}f（x_0，…，x{n-1}）=（x_1，x_2，…，x_n），\x_n=c（x_0，…，x{n-1}），结束{array}$

$C（x_0，…，x{n-1}）=C_0 x_0+。。。+c{n-1}x{n-1}，$

$C（x）=1+C_x+…+C{n-1}x^n$

LFSR序列是

$开始{array}{c}1，1，0，1，0，1，1，0，0，1，1，1，\1，1，0，1，1，0，1，1，0，0，1，0，0，1，1，…。结束{array}$

sage: F = GF(2)
sage: o = F(0)
sage: l = F(1)
sage: key = [l,o,o,l]; fill = [l,l,o,l]; n = 20
sage: s = lfsr_sequence(key,fill,n); s
[1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0]
sage: lfsr_autocorrelation(s,15,7)
4/15
sage: lfsr_autocorrelation(s,15,0)
8/15
sage: lfsr_connection_polynomial(s)
x^4 + x + 1
sage: from sage.matrix.berlekamp_massey import berlekamp_massey
sage: berlekamp_massey(s)
x^4 + x^3 + 1


### 经典密码¶

sage: S = AlphabeticStrings()
sage: S
Free alphabetic string monoid on A-Z
sage: E = SubstitutionCryptosystem(S)
sage: E
Substitution cryptosystem on Free alphabetic string monoid on A-Z
sage: K = S([ 25-i for i in range(26) ])
sage: e = E(K)
sage: m = S("THECATINTHEHAT")
sage: e(m)
GSVXZGRMGSVSZG


sage: S = AlphabeticStrings()
sage: E = TranspositionCryptosystem(S,15);
sage: m = S("THECATANDTHEHAT")
sage: G = E.key_space()
sage: G
Symmetric group of order 15! as a permutation group
sage: g = G([ 3, 2, 1, 6, 5, 4, 9, 8, 7, 12, 11, 10, 15, 14, 13 ])
sage: e = E(g)
sage: e(m)
EHTTACDNAEHTTAH