跳转至

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. 实验规范

每次实验至少记录:

  1. 实验日期。
  2. Python 版本。
  3. 有限域定义。
  4. 候选函数完整表达式。
  5. 参数范围。
  6. 完整 Walsh 谱检验结果。
  7. 运行代码及输出。
  8. 已证明和未证明的结论。