# 数论/位运算构造题

> 何时用：题目要求**构造**满足数论/位运算约束的输入（整除性、模等式、位掩码、幂等式等），而非给密文求明文。**触发条件是约束的性质（数论/位运算 + 要构造输入），不是题目的外壳形式**——外壳可能是白盒脚本、二进制校验、交互服务等多种，分析方法取决于约束本身。

## 1. 识别这类题

| 特征 | 说明 |
|------|------|
| **"构造"而非"攻击"** | 没有"密文"可解，要构造合法输入；区别于分解/求逆/解密 |
| 约束是整除 / 模运算 / 位运算 / 幂 | `int(x) % M == 0`、`x & mask == target`、`pow(x,e,n) == ...` |
| 输入是受限字符集 | flag 内部只含特定字符（如 `[67]`、二进制串、十六进制） |
| 白盒可见验证逻辑（若可见可直接分析约束） | 题目给出 `assert`/脚本/判定函数时可白盒分析；黑盒时需先逆向/交互探测约束 |

**关键区分**：传统密码题给密文求明文（攻击）；本类题给约束求输入（构造）。判断标准是"有没有密文要解"——没有密文、只要求构造满足约束的输入 → 走本文档，**不论题目外壳是什么形式**。

## 2. 通用求解思路

```
1. 实测确认表达式的真实求值（优先级陷阱，见 §4，禁止心算）
2. 把约束写成数学形式（整除性 / 模等式 / 位等式）
3. 利用模运算性质把"构造"问题降维（见 §3）
4. 求出候选后，用题目原始验证逻辑验证（见 §5）
```

## 3. 梅森数 `2^p-1` 的二进制位构造法（核心技巧）

### 3.1 什么时候用

- 模数是 `2^p - 1`（梅森数；**不必是素数**，合数同样适用，只需 `2^p ≡ 1` 性质）
- 输入含一组"单位增量"的可变位（如字符 `a`↔`b` 差 1，或 `0`↔`1` 差 1）
- 约束是 `int.from_bytes(flag) % (2^p - 1) == 0`

### 3.2 原理

- 核心性质：`2^p ≡ 1 (mod 2^p - 1)`，故 `2` 的幂按 `p` 取循环
- 多字节整数 `N = Σ b_j · 256^(L-1-j) = Σ b_j · 2^(8(L-1-j))`
- 模 `M_p`：`2^(8(L-1-j)) ≡ 2^((8(L-1-j)) mod p)`——字节流被"折叠"成 `p` 位循环

### 3.3 关键降维条件

若可变位的位置幂次 `{(8·pos) mod p}` **遍历** `{0,1,...,p-1}`（当 `gcd(8,p)=1` 且可变位数 `== p` 时成立）：

- 单位增量权重集合恰是 `{2^0, 2^1, ..., 2^(p-1)}` 的一个排列——等同一个 `p` 位二进制数的各位
- 目标余数的**二进制表示直接给出**每个增量位取 `0` 还是 `1`
- 把 `2^p` 种组合的爆破降为 `O(p)` 直接构造

### 3.4 构造代码（通用）

```python
def construct_mersenne(prefix: bytes, suffix: bytes, lo: int, hi: int, p: int) -> bytes:
    """
    构造 flag = prefix + 可变部分(n_var=p 个字节, 每个∈{lo,hi}) + suffix,
    使 int.from_bytes(flag, 'big') % (2**p - 1) == 0.
    要求: hi - lo == 1 (单位增量); gcd(8, p) == 1 (幂次遍历全集).
    返回: 构造好的 flag bytes.
    """
    assert hi - lo == 1, "本函数要求单位增量(hi-lo==1); 差值非1时权重整体乘以差值, 需改用格/子集和"
    from math import gcd
    assert gcd(8, p) == 1, "gcd(8,p)!=1 时幂次不遍历全集, 退化为子集和(见 lattice-attacks.md)"
    M = 2**p - 1
    L = len(prefix) + p + len(suffix)          # flag 总长
    base = prefix + bytes([lo]) * p + suffix   # 全取 lo 的基准值
    N_base = int.from_bytes(base, 'big')
    target = (-N_base) % M                      # 需要凑出的余数
    inv8 = pow(8, -1, p)
    chars = [lo] * p
    # target 的第 k 位为 1 => 对应的可变位设为 hi
    for k in range(p):
        if (target >> k) & 1:
            # 可变位第 i 个: 字节位置 j=len(prefix)+i, 幂次 a_i=(8*(L-1-j))%p
            # 解 a_i == k:  i ≡ (L-1-len(prefix)) - k*inv8 (mod p)
            i = (L - 1 - len(prefix) - k * inv8) % p
            chars[i] = hi
    flag = prefix + bytes(chars) + suffix
    assert int.from_bytes(flag, 'big') % M == 0, "构造校验失败"
    return flag

# 示例: prefix=SEKAI{, suffix=}, 可变字符 '6'/'7'(差1), p=67
flag = construct_mersenne(b"SEKAI{", b"}", ord("6"), ord("7"), 67)
print(flag.decode())   # 输出满足 int(...) % (2**67-1) == 0 的 flag
```

### 3.5 不满足降维条件时

- `gcd(8,p) ≠ 1`（如 `p` 是 2 的倍数）→ 幂次不遍历全集 → 退化为**子集和/格问题**，见 `$AGENT_DIR/knowledge-base/lattice-attacks.md`
- 增量差值 `d ≠ 1` → 权重变为 `d·2^{a_i}`；当 `d` 与 `M` 互素时，目标值乘 `d` 的逆元后仍可用二进制位法；不互素时先约去公因子再判断

## 4. Python 运算符优先级陷阱（必读）

位运算与一元运算符（`~`/`-`）、`**` 混用时，表达式真实求值易被误判——题目可能借此隐藏真实模数/常量。**禁止心算，必须 `python -c` 实测**：

| 表达式 | 直觉（错） | 实际（对） | 原因 |
|--------|-----------|-----------|------|
| `~(6+~7)**67` | `(~(6+~7))**67` | `~((6+~7)**67)` | `**` 优先级高于一元 `~` |
| `-2**2` | `(-2)**2 = 4` | `-(2**2) = -4` | `**` 优先级高于一元 `-` |
| `~7` | `8` | `-8` | `~x = -x-1` |
| `2**3**2` | `(2**3)**2=64` | `2**(3**2)=512` | `**` 右结合 |

```bash
# 永远这样确认, 不要猜
python -c "print(~(6+~7)**67)"   # => 147573952589676412927 = 2**67-1
```

## 5. 用题目原始验证逻辑验证（最佳实践）

这类题题目本身包含验证逻辑（白盒时可见），**最可靠的验证 = 把候选输入喂给题目原始验证逻辑**：

```bash
# 把候选输入喂给题目原始验证逻辑（以 assert 形式题目为例）
printf '%s' "$CANDIDATE" | python -c "
assert __import__('re').match('...原题正则...', flag:=input()) and not <原题约束>
print('PASS', flag)
"
```

- **避免重实现验证逻辑**（重实现可能引入与解题同源的 bug，互相印证无意义）
- 原始验证逻辑通过 = 100% 正确（题目就是判据）
- 失败 = 检查构造步骤，不要改验证逻辑

## 决策

```
构造输入 + 无密文 + 数论/位运算约束?
├─ 模数形如 2^p-1 + 单位增量可变位 + gcd(8,p)=1
│    └─ 二进制位构造法 (§3)
├─ 模数形如 2^p-1 但不满足降维条件
│    └─ 退化为子集和/格 (转 lattice-attacks.md)
├─ 约束是位运算 (mask/and/xor)
│    └─ 按位独立求解 (每位约束通常可分离)
└─ 其它数论约束
     └─ 列出数学形式, 用 sympy/sage 求解
```

## 注意

- **模数不必是梅森素数**：`2^67-1` 是合数，照样用 `2^67 ≡ 1` 性质，素性无关
- **字符集增量不一定是 1**：`'0'→'1'`、`'a'→'b'` 差 1 最简单；差 `d` 时权重乘 `d`
- **先实测再推导**：所有"模数是多少""表达式求值"都用 `python -c` 确认，不心算
- **验证用题目原始验证逻辑**：别重实现验证器
