实验 01：从零实现一个玩具有限域

本实验只用于理解代数结构。小素数域、分支、取模运算和普通整数都不具备生产级密码学安全性。

目标

完成一个 Fp<P> 类型，并通过测试亲自确认：

• 加、减、乘之后仍落在 0..P；
• 每个非零元素都有乘法逆元；
• 除法本质上是乘以逆元；
• 拉格朗日插值所需的运算可以由这些基本操作组成。

本章固定使用素数 P = 17。先把每一步算清楚，再在后续实验中换成 Ristretto255 的标量域。

前置知识

• Rust 的结构体、泛型常量、Result 和单元测试；
• 整数余数运算；
• 群、环、域的直观定义。

如果“域”仍然抽象，可以先把它理解为一个有限的钟面：超过 16 就绕回 0，但除 0 外的每个刻度都能做除法。

建议 API 与文件

建议文件：src/toy_field.rs

#![allow(unused)]
fn main() {
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Fp<const P: u64>(u64);

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum FieldError {
    ZeroHasNoInverse,
}

impl<const P: u64> Fp<P> {
    pub fn new(value: u64) -> Self {
        assert!(P > 1, "modulus must be greater than one");
        Self(value % P)
    }

    pub fn value(self) -> u64 {
        self.0
    }

    pub fn add(self, rhs: Self) -> Self {
        // 使用 u128，避免两个 u64 相加时先溢出。
        Self::new(((self.0 as u128 + rhs.0 as u128) % P as u128) as u64)
    }

    pub fn sub(self, rhs: Self) -> Self {
        todo!("先在纸上推导不会发生无符号下溢的写法")
    }

    pub fn mul(self, rhs: Self) -> Self {
        todo!("先扩大到 u128，再取模")
    }

    pub fn pow(self, exponent: u64) -> Self {
        todo!("实现平方-乘算法，而不是循环 exponent 次")
    }

    pub fn invert(self) -> Result<Self, FieldError> {
        todo!("处理 0；对本实验的素数模数使用费马小定理")
    }
}
}

上面的代码是可编译骨架：todo!() 会让代码通过编译，但运行到对应分支时会主动终止。不要把 Fp<P> 的 P 可配置性误解为它能安全支持任意模数；本实验默认调用者保证 P 是素数。

分步任务

1. 画出 F17 的运算表

先不写代码，手算下列结果：

• 15 + 5
• 3 - 8
• 7 * 5
• 3 的逆元

记录“普通整数结果”和“模 17 结果”。如果两者混在一起，后面的 Shamir 插值很容易写错。

2. 实现封闭的加、减、乘

补全 sub 和 mul。对减法，不要直接写 self.0 - rhs.0；先考虑 Rust debug 构建中的无符号下溢。

边界检查：

• Fp::<17>::new(17) 应等于 0；
• 0 - 1 应等于 16；
• 中间乘积用 u128，最后再转回 u64。

3. 实现快速幂

实现平方-乘算法。每处理一位指数，只做一次平方，并在对应位为 1 时多做一次乘法。

不要直接复制现成实现；用注释回答：循环过程中，base、accumulator 和尚未处理的指数分别代表什么？

4. 实现逆元

对于素数 P 和非零 a，费马小定理给出：

\[ a^{P-1}=1 \pmod P \]

请自行推导逆元应该使用哪个指数。0 必须返回 Err(FieldError::ZeroHasNoInverse)，不能静默返回 0。

5. 再决定是否实现运算符

基础测试通过后，可为 Add、Sub、Mul 实现标准 trait。先保留命名方法有一个好处：调试时每一步的语义更显眼。

验收测试

至少写出以下测试；示例中的测试是可编译的，前提是你的模块路径一致。

#![allow(unused)]
fn main() {
#[cfg(test)]
mod tests {
    use super::*;

    type F17 = Fp<17>;

    #[test]
    fn arithmetic_wraps_modulo_p() {
        assert_eq!(F17::new(15).add(F17::new(5)), F17::new(3));
        assert_eq!(F17::new(3).sub(F17::new(8)), F17::new(12));
        assert_eq!(F17::new(7).mul(F17::new(5)), F17::new(1));
    }

    #[test]
    fn every_nonzero_element_has_an_inverse() {
        for raw in 1..17 {
            let a = F17::new(raw);
            let inverse = a.invert().unwrap();
            assert_eq!(a.mul(inverse), F17::new(1));
        }
    }

    #[test]
    fn zero_has_no_inverse() {
        assert_eq!(F17::new(0).invert(), Err(FieldError::ZeroHasNoInverse));
    }

    #[test]
    fn field_laws_hold_for_all_f17_values() {
        for a in 0..17 {
            for b in 0..17 {
                for c in 0..17 {
                    let (a, b, c) = (F17::new(a), F17::new(b), F17::new(c));
                    assert_eq!(a.add(b), b.add(a));
                    assert_eq!(a.mul(b), b.mul(a));
                    assert_eq!(a.mul(b.add(c)), a.mul(b).add(a.mul(c)));
                }
            }
        }
    }
}
}

完成标准：测试全部通过，并且你能解释为什么穷举 F17 是可行的，而对真实标量域不可行。

观察记录

把结果写入实验日志，而不只是让测试变绿：

进阶挑战

1. 用扩展欧几里得算法实现第二种求逆方式，并与快速幂版本逐项比较。
2. 增加 TryFrom<u64> 或更明确的构造 API，区分“规范编码”和“自动约简”。
3. 用 proptest 对更大的素数做性质测试；说明随机性质测试为什么不能代替证明。
4. 尝试把 P 改成合数 15，找出第一个没有逆元的非零元素，并解释失败原因。

安全警告

• 该实现不是常量时间：分支、指数位和普通整数运算都可能泄漏信息。
• P 没有经过素数验证，且这里只为中间运算选用了 u128；它不是通用大整数有限域。
• 禁止把本章代码用于密钥、真实签名、钱包或任何资产场景。
• 后续真实曲线实验必须使用 curve25519-dalek 提供的 Scalar 和点运算，不要自行实现曲线或模数约简。