A Factoring Algorithm Using the Continued Fraction Expression

1 Citations 11 References
  • KOBAYASHI Kunikatsu
    Department of Electrical and Information Engineering, Faculty of Engineering, Yamagata University
  • TANAKA Atsushi
    Department of Electrical and Information Engineering, Faculty of Engineering, Yamagata University

Bibliographic Information

Other Title
  • 連分数表現を用いる素因数分解アルゴリズム

Search this article

Description

We propose a factoring algorithm using the continued fraction expression. In this algorithm we use a function h_i(X)=(s_i+t_i⌊√<nx>⌋)^2-t^2_inx which Contains a value under a decimal point of √<nx>, where s_i/t_i ≈ √<nx>-⌊√<nx>⌋. In the case of l_<i+1>≫1, the function h_i(X) is related to a coefficient l_<i+1> of the continued fraction by the following equation |h_i(x)|=⌊2√<nx>/l_<i+1>⌋The conventional factoring algorithms are one-dimensional searching algorithms, but this method is a two-dimensional searching algorithm which has two variables x and i.

Journal

  • Technical report of IEICE. ISEC

    Technical report of IEICE. ISEC 95 (172), 19-27, 1995-07-21

    The Institute of Electronics, Information and Communication Engineers

Citations (1)*help

See more

References(11)*help

See more

Keywords

Details 詳細情報について

  • CRID
    1571135652340625280
  • NII Article ID
    110003297013
  • NII Book ID
    AN10060811
  • Text Lang
    ja
  • Data Source
    • CiNii Articles

Report a problem

Back to top