| 引用本文: | 顾海华,谷大武,谢文录,等.使用三个数域的数域筛算法.[J].国防科技大学学报,2012,34(2):1-5.[点击复制] |
| GU Haihua,GU Dawu,XIE Wenlu,et al.The number field sieve with three number fields[J].Journal of National University of Defense Technology,2012,34(2):1-5[点击复制] |
|
| |
|
|
| 本文已被：浏览 7722次 下载 6467次 |
| 使用三个数域的数域筛算法 |
| 顾海华1,2, 谷大武3, 谢文录2, 李升1, 严家驹1 |
|
(1.上海交通大学 计算机科学与工程系，上海 200240;2.上海华虹集成电路有限责任公司，上海 201203;3.1.上海交通大学 计算机科学与工程系，上海 200240)
|
| 摘要: |
| 大整数分解难题是RSA密码的数学安全基础。目前数域筛算法是分解365比特以上大整数的最有效方法，然而它的时间复杂度仍然是亚指数的。对于目前普遍使用的1024比特以上大整数，数域筛算法还不能分解，所以研究数域筛算法具有重要的意义。现有的一般数域筛算法普遍使用两个数域，对多个数域的研究极少。一般数域筛算法经过修改可以使用三个数域，即两个代数数域和一个有理数域。分析表明：修改后的数域筛算法与原来的一般数域筛算法在时间复杂度上处于同一量级。但修改后的数域筛算法有更多地方可以合并计算，所以计算速度更快了。通过两个实验也验证了这一结论。 |
| 关键词: 公钥密码 RSA密码 整数分解 数域筛算法 |
| DOI： |
| 投稿日期：2011-09-14 |
| 基金项目:教育部博士点专项基金项目(200802480019) |
|
| The number field sieve with three number fields |
|
(1.Department of Computer Science & Engineering, Shanghai Jiaotong University, Shanghai 200240, China;2.Shanghai Huahong Integrated Circuit Co., Ltd. , Shanghai 201203, China)
|
| Abstract: |
| The mathematical security of the RSA cryptosystem is based on the problem of factoring large integers. At present, the number field sieve is the most efficient algorithm known for factoring integers larger than 365 bits, while its time complexity is still sub-exponential. Integers larger than 1024 bits, which are widely used in RSA cryptosystem, cannot be factored by means of the number field sieve. So it is significant to study the number field sieve.Now, the general number field sieve often uses two number fields, while multiple number fields are seldom considered. The general number field sieve, through adaptation, can use three number fields, i.e. two algebraic number fields and one rational number field. Analysis shows that the time complexity of the modified number field sieve and the general number field sieve are at the same level. However, the modified number field sieve can combine more computation, so it can save more time in practice. Finally, the result is verified by two experiments. |
| Keywords: public key cryptography RSA cryptosystem integer factorization number field sieve algorithm |
|
|
|
|
|
