A Factoring Algorithm of Integers N=p^r×q Using Jacobi Signature(<Special Issue>"Algorithmic Number Theory and Its Applications, Part 1")

DOI Web Site 11 References

Bibliographic Information

Other Title
  • Jacobi signatureを用いたN=p^r×q型の合成数に対する素因数分解アルゴリズム(<特集>数論アルゴリズムとその応用,その1)
  • Jacobi signatureを用いたN=pr×q型の合成数に対する素因数分解アルゴリズム
  • Jacobi signature オ モチイタ N pr qガタ ノ ゴウセイスウ ニ タイスル ソインスウ ブンカイ アルゴリズム

Search this article

Description

This paper presents an efficient algorithm of factoring of integers N=p^r×q for large r. By using the Jacobi signature, our algorithm can be estimated to be much faster than Chida et al.'s algorithm which can factor integers N=p^r×q efficiently if r is large and its factors are small. Chida et al. showed that their algorithm was faster than the elliptic curve method under some conditions. Therefore, this paper insists that the parameter r has to be chosen carefully when we use the encryption or signature scheme based on the hardness of factoring of integers N=p^r×q.

Journal

References(11)*help

See more

Details 詳細情報について

Report a problem

Back to top