私钥 d 正是作为 e 关于模 φ(n) 的乘法逆元而存在的，而 φ(n) 又只能通过知道 p 和 q 来计算。RSA 的安全性依赖于大整数分解的困难性：攻击者知道 n 但无法高效分解出 p 和 q，因此无法计算 φ(n)，也就无法求出私钥 d。：上承质因数分解（p 和 q → φ(n)），下启私钥计算（φ(n) 和 e → d）。它是整个算法正确性的保证，也是安全性的前提。当 gcd(e, φ(

（维纳攻击）恢复私钥。# 由 φ(n) = n - p - q + 1 得 s = p + q = n - φ(n) + 1。# 由 ed = 1 + k·φ(n) 得 φ(n) = (ed - 1) / k，必须为整数。核心公式：|e/n - k/d| < 1/(2d²)，k/d 必为 e/n 的连分数收敛。：对于 n = p * q（p、q 为素数），φ(n) = (p-1)*(q-1)。保证

==================== 步骤 1: 对 n 开 10 次方求 r 近似值 ====================# ==================== 步骤 2: 在近似值附近搜索精确的 r ====================# ==================== 步骤 3: 用 r 重建 p 和 q ====================# =======

print(f"欧拉定理保证：ed ≡ 1 (mod φ(n)) → m^ed ≡ m (mod n)")本文将按照"数学定义 → 定理证明 → 密码学应用 → 工程实践"的路线，系统梳理欧拉定理在密码学中的核心地位。理解欧拉定理，不仅是为了看懂 RSA 的证明，更是掌握现代密码学"从数论到安全"这一底层思维范式的关键一步。"""扩展欧几里得算法，返回 (gcd, x, y) 使得 ax + by