n = p * q 的因數分解之研究

Abstract

RSA密碼系統(RSA Cryptosystem)是使用最為廣泛的公鑰密碼系統之一，其安全性乃建立在大整數難以分解為其質因數乘積的事實之上，此一事實並被稱為RSA假定(RSA assumption)。一般相信沒有確定型的圖靈機(deterministic Turing machine，簡稱DTM)可在多項式時間內破解RSA假定，多項式時間的演算法若被發現，RSA密碼系統將變得不再安全。因為如此，許多科學家致力於研究有效率的分解演算法。目前所知，分解小於110位數的大數時，「二次篩選法(quadratic sieve factoring algorithm，簡稱QS)」是最快的通用演算法。受限於時間與硬體資源，我們主要著眼於QS的一種變型，稱之為「複數多項式二次篩選法(multiple polynomial quadratic sieve，簡稱MPQS)」。為了確認RSA假定的強度，我們提出一個方法來加速MPQS的篩選程序，其實驗結果將有助於分析RSA抵抗現行分解技術的強度，同時可被納入實作RSA密碼系統時的考量。

The RSA Cryptosystem is one of the most used public-key cryptosystems. The security it rests on the fact that it is computationally infeasible to factor a large integer into its component primes. This fact is referred to as the RSA assumption. It is believed that there is no deterministic Turing machines (DTM) that can break the RSA assumption in polynomial time. If a polynomial-time algorithm is found, the RSA Cryptosystem would be insecure. Owing to this, many scientists have devoted themselves to researching efficient factoring algorithms. So far, the quadratic sieve factoring algorithm (abbreviated to QS) is the fastest known general-purpose method for factoring numbers having less than about 110 digits. Restricted by time and computer hardware, we focus on one of the variants of the QS, called the multiple polynomial quadratic sieve (MPQS). To ensure the strength of the RSA assumption, we propose a scheme to enhance the sieving procedure of the MPQS. The experimental results are contributive to the analyses of the strength of the RSA assumption against the modern factoring technology and should be taken into consideration on future cryptographic implementations based on the RSA cryptosystem.