A New Factoring Method of Integers N = p^r x q for Large r(Special Section on Discrete Mathematics and Its Applications)

概要

論文の詳細を見る
Since the invention of the RSA scheme, a lot of public-key encryption and signature schemes based on the intractability of integer factoring have been proposed. Most employ integers of the form N = p × q, such as the RSA scheme, but some employ integers of the form N = p^r × q. It has been reported that RSA decryption speed can be greatly improved by using N = p^r × q integers for large r. On the other hand, Boneh et al. proposed a novel integer factoring method for integers such as N = p^r × q for large r. This factoring algorithm, the so-called Lattice Factoring Method, is based on the LLL-algorithm. This paper proposes a new method for factoring integers of the form N = p^r × q for large r and gives a new characterization of r such that factoring integers N = p^r × q is easier. More precisely, the proposed method strongly depends on the size and smoothness of the exponent, r. The theoretical consideration of and implementation of our method presented in this paper show that if r satisfies a certain condition our method is faster than both Elliptic Curve Method and Lattice Factoring Method. In particular, the theoretical consideration in this paper mainly employs the techniques described in the excellent paper by Adleman, Pomerance and Rumely that addresses primality testing.
社団法人電子情報通信学会の論文
2002-05-01