In this paper, we report efficient implementations of the linear sieve and the cubic sieve methods for computing discrete logarithms over prime fields. We demonstrate through empirical performance measures that for a special class of primes the cubic sieve method runs about two times faster than the linear sieve method even in cases of small prime fields of the size about 150 bits. We also provide a heuristic estimate of the number of solutions of the congruence $X^{3}?=?Y^{2}Z$ (mod p) that is of central importance in the cubic sieve method.
展开▼
机译:在本文中,我们报告了用于在素数域上计算离散对数的线性筛和三次筛方法的有效实现。我们通过经验性能度量证明,对于特殊种类的质数,即使在大小约为150位的较小质数场的情况下,三次筛方法的运行速度也比线性筛方法快约两倍。我们还提供了对同余$ X ^ {3}?=?Y ^ {2} Z $(mod p)的解数的启发式估计,这在三次筛方法中至关重要。
展开▼