概述

三个数学难题

大整数因数分解问题

1. 给定两个素数$p$和$q$，计算其乘积$n=p\times q$是容易的；
2. 但是从$n$分解出$p$和$q$是非常困难的。

离散对数问题

已知有限循环群$G=\lt g\gt=\{g^k\mid k=0,1,2,…\}$及其生成元$g$和阶$n=|G|$。

1. 给定整数$a$计算元素$g^a=h$很容易；
2. 给定元素$h$，计算整数$x$，$0\leq x\leq n$，使得$g^x=h$非常困难。

椭圆曲线离散对数问题

已知有限域$F_p$上的椭圆曲线群

$$E(F_p)=\{(x,y)\mid\in F_p\times F_p,\quad y^2=x^3+ax+b,\quad a,b\in F_p\}\cup\{O\}$$

及点$P=(x,y)$的阶为一个大素数。

1. 给定整数$a$，计算点$aP=(x_a,y_a)=Q$很容易；
2. 给定点$Q$,计算整数$x$，使得$xP=Q$非常困难。