Python 计算实验
1. 实验目的
使用 Python 计算 Boolean 函数的:
- 真值表。
- Hamming 重量。
- Walsh 谱。
- 非线性度。
- Bent 性质。
2. Walsh 变换
设
\[
f:\mathbb F_2^n\to\mathbb F_2.
\]
其 Walsh 变换为
\[
W_f(a)=
\sum_{x\in\mathbb F_2^n}
(-1)^{f(x)+a\cdot x}.
\]
可以使用快速 Walsh–Hadamard 变换计算全部谱值。
3. Python 验证程序
下面的程序不依赖第三方库。
def walsh_spectrum(truth):
n = len(truth)
if n == 0 or n & (n - 1):
raise ValueError("真值表长度必须是2的幂")
w = [1 - 2 * int(v) for v in truth]
h = 1
while h < n:
for i in range(0, n, 2 * h):
for j in range(i, i + h):
a, b = w[j], w[j + h]
w[j] = a + b
w[j + h] = a - b
h *= 2
return w
def check_bent(truth):
n = len(truth)
spectrum = walsh_spectrum(truth)
if n == 0 or n & (n - 1):
raise ValueError("真值表长度必须是2的幂")
dimension = n.bit_length() - 1
if dimension % 2:
return False
target = 2 ** (dimension // 2)
return all(abs(v) == target for v in spectrum)
def hamming_weight(truth):
return sum(truth)
def nonlinearity(truth):
spectrum = walsh_spectrum(truth)
return (len(truth) - max(map(abs, spectrum))) // 2
# 一个已知的四变量 Bent 函数
# f(x) = x0*x1 + x2*x3
truth = []
for x in range(16):
x0 = (x >> 0) & 1
x1 = (x >> 1) & 1
x2 = (x >> 2) & 1
x3 = (x >> 3) & 1
truth.append((x0 & x1) ^ (x2 & x3))
print("Bent:", check_bent(truth))
print("Walsh谱:", walsh_spectrum(truth))
print("Hamming重量:", hamming_weight(truth))
print("非线性度:", nonlinearity(truth))
4. 实验记录
实验 A:已知 Bent 函数测试
目标:验证程序正确性。
预期:
- Bent 判断为 True。
- 所有 Walsh 系数绝对值为 4。
- Hamming 重量为 6。
- 非线性度为 6。
实验 B:十变量候选函数
研究对象:
\[
T_h(x,y)=x^6+xy+h(y).
\]
候选多项式:
\[
h(y)=y^{17}+y^{24}+y^{26}.
\]
此前计算记录:
| 项目 | 结果 |
|---|---|
| 变量数 | 10 |
| Walsh 谱绝对值 | 32 |
| Hamming 重量 | 528 |
| 非线性度 | 496 |
| 代数次数 | 5 |
这些数据属于此前的候选函数实验记录, 不是上面的四变量示例程序的输出。
后续需要补充完整的有限域运算、 特殊切片定义和真值表生成程序。
5. 实验规范
每次实验至少记录:
- 实验日期。
- Python 版本。
- 有限域定义。
- 候选函数完整表达式。
- 参数范围。
- 完整 Walsh 谱检验结果。
- 运行代码及输出。
- 已证明和未证明的结论。