SageMath 中 Zmod 表达式求值方法

本文介绍在 SageMath 中对含平方根等运算的符号表达式，在有限环 ℤ/nℤ（即 `Zmod(n)`）上安全、准确求值的方法，涵盖自动解析字符串表达式、处理多值平方根、规避符号歧义等关键实践。

在 SageMath 中，直接对形如 "-1 / sqrt(7) + 5" 的字符串表达式在模 9 下求值并非开箱即用——因为 Zmod(9) 是一个非域（9 不是素数），其元素不构成域，平方根可能有 0、1 或多个解（如 7 在 Zmod(9) 中有两个平方根：4 和 5），且标准符号计算不会自动将整数字面量映射到模类中。

✅ 正确求值的前提：显式构造 Zmod 元素

首先明确：Zmod(n) 的元素需显式构造。例如：

sage: R = Zmod(9)
sage: a = R(7)   # 将整数 7 转为 Zmod(9) 中的元素
sage: a.sqrt()   # 返回一个平方根（默认最小非负解）
4
sage: a.sqrt(all=True)  # 返回所有平方根
[4, 5]

注意：sqrt() 方法仅对可逆或有平方根的元素有效；若 a 在 Zmod(9) 中无平方根（如 R(2)），调用 .sqrt() 会报错。

? 自动解析并求值：基于 Symbolic Ring 的递归转换

为支持字符串表达式（如 "-1 / sqrt(7) + 5"）的自动求值，推荐使用 Sage 的符号环 SR 作为安全解析器，再通过递归遍历表达式树，将所有数值节点替换为 Zmod(9) 元素：

sage: def zmod_eval(expr, modulus=9):
....:     R = Zmod(modulus)
....:     if expr.is_numeric():
....:         return R(expr)
....:     op = expr.operator()
....:     if op is None:
....:         return expr  # 变量或未识别符号（需额外处理）
....:     operands = [zmod_eval(arg, modulus) for arg in expr.operands()]
....:     return op(*operands)
....:
sage: expr = SR("-1 / sqrt(7) + 5")
sage: zmod_eval(expr)
7

该函数成功将 sqrt(7) 解析为 R(7).sqrt()（即 4），进而计算 -1/4 + 5 ≡ -1 * 4^{-1} + 5 (mod 9)。由于 4*7 ≡ 1 (mod 9)，故 4^{-1} = 7，因此 -1*7 + 5 = -2 ≡ 7 (mod 9)。

⚠️ 处理多值平方根：返回全部结果

因 sqrt(7) 在 Zmod(9) 中有两个解（4 和 5），若需获取所有可能结果，应修改函数以支持分支展开：

sage: def zmod_eval_all(expr, modulus=9):
....:     R = Zmod(modulus)
....:     if expr.is_numeric():
....:         return [R(expr)]
....:     op = expr.operator()
....:     if op is None:
....:         raise ValueError(f"Unsupported symbolic object: {expr}")
....:     # 特殊处理 sqrt：识别 pow(x, 1/2) 形式
....:     if str(op) == 'pow' and len(expr.operands()) == 2:
....:         base, exp = expr.operands()
....:         if exp == SR(1/2) or exp == SR(0.5):
....:             vals = zmod_eval_all(base, modulus)
....:             results = []
....:             for v in vals:
....:                 try:
....:                     roots = v.sqrt(all=True)
....:                     results.extend(roots)
....:                 except ValueError:
....:                     pass  # 无平方根，跳过
....:             return results
....:     # 一般二元/多元运算
....:     operand_lists = [zmod_eval_all(arg, modulus) for arg in expr.operands()]
....:     from itertools import product
....:     results = []
....:     for args in product(*operand_lists):
....:         try:
....:             res = op(*args)
....:             results.append(res)
....:         except (ZeroDivisionError, ValueError):
....:             continue
....:     return list(set(results))  # 去重
....:
sage: expr = SR("-1 / sqrt(7) + 5")
sage: sorted(zmod_eval_all(expr))
[3, 7]

输出 [3, 7] 正确对应两个平方根分支：

• 若 sqrt(7) = 4 → -1/4 + 5 ≡ -1×7 + 5 = -2 ≡ 7
• 若 sqrt(7) = 5 → -1/5 + 5，而 5^{-1} ≡ 2 (mod 9)（因 5×2=10≡1），故 -1×2 + 5 = 3

? 注意事项与最佳实践

• 避免 SR 中的幂歧义：sqrt(x) 在 SR 内部被表示为 x^(1/2)（即 pow(x, 1/2)），因此需检查 operator() 是否为 pow 且指数为 1/2，而非依赖 .function() 或字符串匹配。
• 非素数模数的限制：Zmod(n) 在 n 含平方因子（如 9 = 3²）时不是域，部分元素不可逆或无平方根；建议预先验证 R(a).is_square()。
• 性能与可维护性：对于高频或复杂表达式，更稳健的方式是在生成表达式阶段就直接使用 Zmod(n) 对象（如 R(-1) / R(7).sqrt() + R(5)），而非后期解析字符串——这能彻底规避符号解析歧义和运行时错误。
• 替代方案：若需更严格的代数结构支持（如有限域 GF(p) 上的唯一平方根），可改用 GF(p)（当 p 为奇素数时，sqrt() 总返回唯一主根），但 Zmod(n) 是处理合数模的唯一原生选择。

综上，SageMath 完全支持在 Zmod 上求值含平方根的表达式，关键在于显式类型转换 + 符号树遍历 + 多值分支管理。合理封装后，即可构建稳定可靠的模算术表达式求值管道。