整数分解问题

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.

Eureka moment!

这里对数学问题困难性的定义又与上面的算法数论 (algorithmic number theory) 或计算机科学领域的定义不同，是以实验来描述的。是不是很有加密学的特色？

这里还要注意一个概念：密码学假设 (assumption)，它将某个数学问题的困难性归约到实验中的一个高效 (efficient) 算法的存在性上。对于大数质因数分解问题 (Factoring problem)，其困难性被某个高效的 GenModulus 算法的存在保证。