论文部分内容阅读
Ⅰ.引言 1870年Bouniakowsky公布了一种解同余式a~x=bMOD(q)的算法。虽然他的算法含有一些可用于小数字的巧妙想法,但这种算法的渐近复杂性为0(q).尽管这种算法的历史很长,但对于离散对数问题从来也没有出现过快速算法,而且已公布的最好算法(由Shanks提出的)需要0(q~1/2)时间和空间。最近几年,由于这个问题在密码术方面的应用,它已经重新引起人们的兴趣。特别是,Diffie-Hellman公开密钥分配体制的保密性“关键地依赖于计算MOD q对数的难度”。对于这种问题我们提出一种新算法,这种算法在优于0(qε)(对于所有ε>0而言)的随机时间(RTIME)内运行。虽然对这种新算法没有努力提出最有效的体现形式,但是对于中等大小的数这种算法无疑是实用的,而对于Diffie—Hellman方案有了一些结果。我们将在Ⅲ节中讨论这些结果。
I. INTRODUCTION Bouniakowsky published an algorithm for solving the congruence a ~ x = bMOD (q) in 1870. Although his algorithm contains some ingenious ideas that can be used for small numbers, the asymptotic complexity of this algorithm is 0 (q). Although this algorithm has a long history, it has never been fast for discrete logarithms Algorithm, and the best known algorithm (proposed by Shanks) requires 0 (q ~ 1/2) time and space. In recent years, it has rekindled interest due to its use in cryptography. In particular, the confidentiality of the Diffie-Hellman public key distribution system “critically depends on the difficulty of computing MOD q logarithms.” We propose a new algorithm for this problem, which runs within a random time (RTIME) better than 0 (qε) for all ε> 0. Although no effort has been made to propose the most efficient implementation of this new algorithm, the algorithm for medium-sized numbers is undoubtedly useful, and has some results for the Diffie-Hellman scheme. We discuss these results in Section III.