
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

A New Factoring Method of Integers N=p^{r} q for Large r
Koji CHIDA Shigenori UCHIYAMA Taiichi SAITO
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E85A
No.5
pp.10501053 Publication Date: 2002/05/01
Online ISSN:
DOI:
Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: factoring, Carmichael function, Chinese remainder theorem, AdlemanPomeranceRumely primality test,
Full Text: PDF>>
Summary:
Since the invention of the RSA scheme, a lot of publickey 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 socalled Lattice Factoring Method, is based on the LLLalgorithm. 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.

