现代公钥密码学基于的三大数学问题

大整数因数分解问题

给定两个大素数p,q,计算乘积 $p\ast q=n$很容易；给定大整数n，求n的素因素p,q使得 $n=p\ast q$非常困难.

离散对数问题

已知 a; 计算 g^a = h；得出h很简单 已知 h; 计算 g^a = h；得出a非常困难

椭圆曲线离散对数问题（转）

已知有限域F_p上的椭圆曲线点群 $$E(F_p)=(x,y)\in F_p\times F_p\mid y²=x³+ax+b,a,b\in F_p\cup O$$ 点P=(x,y)的阶为一个大素数. Ⅰ）给定整数a，计算整数x，使得xP=(x_a,y_a)=Q很容易； Ⅱ）给定点Q，计算整数x，使得xP=Q非常困难. 例3 P=10823是一个素数，有限域F_p=Z/pZ上的椭圆曲线点群 $$E(F_p)=(x,y)\in F_p\times F_p\mid y²=x³+3x+7\cup O$$ $$\mid E(F_p)\mid =100482=2\cdot 3\cdot 16747.E(F_p)$$ 的生成元为$P_0=(1,8811)$ 点$P=6P_0=(62046,14962)$的阶为素数16747。 Ⅰ) 给定a=1007，计算aP=(80726,17229)=Q很容易； Ⅱ) 给定点Q=(80726,17229)，求整数x使得xP=Q很困难。