On Improving Integer Factorization and Discrete Logarithm Computation using Partial Triangulation
On Improving Integer Factorization and Discrete Logarithm Computation using Partial Triangulation
复制标题
利用部分三角剖分改进整数分解和离散对数计算
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Fabrice Boudot
中科院分区：
文献类型：
--
作者：
Fabrice Boudot
数域筛法是求解素数域上的整数分解和离散对数问题的最著名算法。本文对数域筛法的各个步骤提出了一些新的改进。我们将这些改进应用于当前的768位离散对数记录，并表明我们能够使用这些改进来执行约1260核心·年的总计算时间，而不是使用该问题的最佳已知参数的2350核心·年。此外，我们表明，预计算阶段的768位离散对数问题，例如，允许建立一个大规模的解密工具，由奥克利组1保护的加密流量，是可行的，在合理的时间内使用2000年之前可用的技术。
The number field sieve is the best-known algorithm for factoring integers and solving the discrete logarithm problem in prime fields. In this paper, we present some new improvements to various steps of the number field sieve. We apply these improvements on the current 768bit discrete logarithm record and show that we are able to perform the overall computing time in about 1260 core·years using these improvements instead of 2350 core·years using the best known parameters for this problem. Moreover, we show that the pre-computation phase for a 768-bit discrete logarithm problem, that allows for example to build a massive decryption tool of IPsec traffic protected by the Oakley group 1, was feasible in reasonable time using technologies available before the year 2000.