Carmichael 函数 \(\lambda(n)\)
定义：
对于正整数 \(n\)，Carmichael 函数 \(\lambda(n)\) 定义为最小的正整数 \(m\)，使得对于所有与 \(n\) 互素的整数 \(a\)，都有：
\(
a^m \equiv 1 \pmod{n}
\)
性质：
- \(\lambda(n)\) 是欧拉函数 \(\varphi(n)\) 的“最小指数”版本。
- 若 \(n = p^k\) 是奇素数的幂，则 \(\lambda(p^k) = \varphi(p^k) = p^{k-1}(p-1)\)。
- 若 \(n = 2^k\)，则：
\( \lambda(2) = 1,\quad \lambda(4) = 2,\quad \lambda(2^k) = 2^{k-2} \quad (k \geq 3) \) - 若 \(n = ab\)，且 \(\gcd(a,b) = 1\)，则：
\( \lambda(ab) = \mathrm{lcm}(\lambda(a), \lambda(b)) \)
复合剩余问题
Composite Residuosity Problem, \(CR[n]\)）
定义：
设 \(n = pq\) 是两个大素数的乘积。称一个整数 \(z\) 是模 \(n^2\) 的 \(n\) 次剩余，如果存在整数 \(y\) 使得：
\(
y^n \equiv z \pmod{n^2}
\)
性质：
- 所有模 \(n^2\) 的 \(n\) 次剩余构成乘法群 \(Z_{n^2}^*\) 的一个子群。
- 每个 \(n\) 次剩余 \(z\) 恰好有 \(n\) 个不同的 \(n\) 次根。
- 存在唯一的 \(n\) 次根小于 \(n\)。
单位根与复合剩余类
模 \(n^2\) 的 \(n\) 次单位根：
- 形如 \((1+n)^x \equiv 1 + nx \pmod{n^2}\) 的元素是模 \(n^2\) 的 \(n\) 次单位根。
- 这些元素构成一个阶为 \(n\) 的循环子群。
复合剩余类函数 \(F_g\)
定义：
\(
F_g(x, y) = g^x y^n \mod n^2
\)
其中：
- \(g \in Z_n^*\)，且其阶是 \(n\) 的非零倍数，
- \(x \in Z_n\)，\(y \in Z_n^*\)。
性质：
- 若 \(g\) 的阶是 \(n\) 的非零倍数，则 \(F_g\) 是双射。
- 该函数诱导了一个从 \(Z_{n^2}^*\) 到 \(Z_n\) 的群同态：
\( [w]_g = x \iff w = g^x y^n \mod n^2 \) - 该映射满足：
\( [w_1 w_2]_g = [w_1]_g + [w_2]_g \pmod{n} \)
复合剩余类问题（\(Class[n]\)）
定义：
给定 \(w \in Z_{n^2}^*\) 和 \(g \in B\)（其中 \(B\) 是满足某些阶条件的元素集合），计算：
\(
[w]_g
\)
即找到 \(x\) 使得 \(w = g^x y^n \mod n^2\)
随机自归约性：
- \(Class[n]\) 在 \(w\) 和 \(g\) 上都是随机自归约的
- 即任意实例可以转化为一个随机实例，且解的结构保持一致
与因式分解的关系
定理：
- 如果能够分解 \(n\)，则可以计算 \(\lambda(n)\)，进而求解 \(Class[n]\)
- 如果能破解 RSA[n, n]（模数为 \(n\)、指数为 \(n\) 的 RSA），则也能求解 \(Class[n]\)
Paillier 加密的数学基础
加密：
\(
c = g^m r^n \mod n^2
\)
其中：
- \(m\) 是明文，
- \(r\) 是随机数。
解密：
\(
L(c^\lambda \mod n^2) = \lambda \cdot [c]_{1+n}
\)
\(
m = \frac{L(c^\lambda \mod n^2)}{L(g^\lambda \mod n^2)} \mod n
\)