三大数学难题

在信息安全领域应用广泛的三大数学难题

No1. 大整数因素分解问题

• 已知两个大素数 p,q，求 N=pq 很容易。
• 已知N为两个大素数的积，求 p 和 q 非常困难。

典型应用: RSA

No2. 离散对数问题

已知有限循环群 \(G=<g>=\{g^k| k=0,1,2,\cdots\}\) 及其生成元 g 和阶 n=|G|。

• 给定整数 a，求 \(g^a = h\) 很容易。
• 给定元素 h，求整数 \(x, 0\leq x\leq n\) ，使得 \(g^x = h\) 非常困难。

典型应用：Diffie-Hellman

No3. 椭圆曲线离散对数问题

已知有限域 \(F_p\) 上的椭圆曲线群 \(`E(F_p) = \{(x,y)| \in F_p \times F_p, y^2 = x^3 + ax + b, a,b \in F_p\} \cup \{O\}`\) 及点 \(P=(x,y)\) 的阶为一个大素数。

• 已知 a ，求点 \(aP=(x_a,y_a)=Q\) 很容易。
• 已知点 Q，求整数 x，使得 \(xP=Q\) 非常困难。

可见密码学很多都是在和大素数打交道。

---

详见：信息安全数学基础