剩余系

• 完全剩余系 (CRS)
  • 定义：模 $m$ 的 $m$ 个不同余代表元的集合（如 $\{0,1,\dots ,m-1\}$）。
  • 性质：若 $(a,m)=1$，则 $ax+b$ 也是模 $m$ 的完全剩余系。
• 简化剩余系 (RRS)
  • 定义：模 $m$ 的完全剩余系中与 $m$ 互素的元素集合。
  • 大小：元素个数为欧拉函数 $\varphi (m)$。
  • 群结构：模 $m$ 的简化剩余系关于乘法构成交换群（即 $U_m$ 或 ${\mathbb{Z}}_m^{\ast }$）。
• ⭐ 核心定理（降幂工具）
  • 欧拉定理：若 $(a,m)=1$，则 $a^{\varphi (m)}\equiv 1(\mathrm{mod}m)$。
    • 应用：RSA 算法的核心理论依据。
  • 3.1 费马小定理：若 $p$ 为素数，则 $a^p\equiv a(\mathrm{mod}p)$；若 $p\nmid a$，则 $a^{p-1}\equiv 1(\mathrm{mod}p)$。