A New Factoring Method of Integers N = p^r×q for Larger r

CHIDA Koji, UCHIYAMA Shigenori, SAITO Taiichi

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.

A New Factoring Method of Integers N = p^r×q for Larger r

この論文をさがす

説明

収録刊行物

被引用文献 (2)*注記

参考文献 (11)*注記

キーワード

詳細情報詳細情報について

書き出し

問題の指摘

A New Factoring Method of Integers N = p^r×q for Larger r

この論文をさがす

説明

収録刊行物

被引用文献 (2)*注記

参考文献 (11)*注記

キーワード

詳細情報 詳細情報について

書き出し

問題の指摘

詳細情報詳細情報について