Factoring Problem.
Factoring could be viewed as the inverse operation of multiplication. Multiplying two primes $p$ and $q$ as $N=p\times q$ is easy, while factorizing $N$ to derive $p$ and $q$ is hard.
Factoring the product of two primes: Given $N=pq$, where $p,q$ are primes, find $p$ and $q$.
Factoring Experiment
Cryptographically, the hardness of the factoring problem is indicated by the factoring experiment $\mathtt{Factor}_{\mathscr{A}, Genmodulus}(n)$, where GenModulus is an efficient (polynomial-time) algorithm that, on input $1^n$, outputs $(N,p,q)$ where $N=pq$, and $p,q$ are $n$-bit primes except with negligible probability.
Adversary $\mathscr{A}$ with $N$ needs to efficiently compute the corresponding $p,q$.
Definition. Factoring is hard relative to GenModulus if for all probabilistic polynomial-time algorithm $\mathscr{A}$, there exists a negligible $\varepsilon(n)$ that $\Pr[\mathtt{Factor}_{\mathscr{A}, GenModulus}(n)=1]\leq \varepsilon(n)$.
The Factoring Assumption is the assumption that there exists a GenModulus relative to which factoring is hard.
这里对数学问题困难性的定义又与上面的算法数论 (algorithmic number theory) 或计算机科学领域的定义不同，是以实验来描述的。是不是很有加密学的特色？
这里还要注意一个概念：密码学假设 (assumption)，它将某个数学问题的困难性归约到实验中的一个高效 (efficient) 算法的存在性上。对于大数质因数分解问题 (Factoring problem)，其困难性被某个高效的 GenModulus 算法的存在保证。