高速剰余変換による多数桁乗算 High-precision Multiplication by Fast Modulo Transformation

この論文にアクセスする

この論文をさがす

著者

抄録

多数桁乗算に関する計算アルゴリズムを提案する.そのアルゴリズムは高速フーリエ変換(FFT)に剰余理論を取り込んだ方法を基礎にした.基礎とする方法を高速剰余変換(Fast Modulo Transformation,FMT)と名付ける.FMTは 1 の原始 n 乗根 ω の上に作成したもので,複素数だけでなく整数でも定義できる.ωを複素数にするとFMTはFFTと同じ計算式になる.FMTは剰余理論に基づいているため多数桁乗算への応用に対する見通しが良い. 多数桁乗算へのFMTの応用として整数FMT,巡回乗算,2段階FMT,複素FMTの直接利用および分割乗算を示す.整数FMTによる巡回乗算は ±1 の巡回だけでなく自然数 α に対して ±α で巡回する乗算も可能と判明した.さらに,多数桁乗算の入力値を m 個に分割し,互いに異なる m 個の自然数 α を用いて,±α で巡回する 2m 個の分割した乗算から元の多数桁乗算を復元することが可能となる.多数桁乗算に2段階FMTおよび分割乗算を利用すると使用メモリ量を大きく削減できる.In this paper, I would like to present new algorithms for high-precision multiplication method. They are based on Fast Fourier Transformation (FFT) and remainder theorem. The based method is called a Fast Modulo Transformation (FMT). The FMT is composed on a primitive root of one (ω) and It is possible to define not only by a complex number but by a integer.If ω is a complex number, the computational formulation of the FMT is same as the FFT. The FMT has the wide scope about a high-precision multiplication, becouse it is based on remainder theorm. I present integer FMT, cyclic multiplications, two level FMT, direct use of complex FMT and divide multiplications for the FMT application. If α are natural numbers, I show that the FMT can achieve not only ±1 cyclic multiplication but ±α cyclic multiplications.In addition, the FMT can divide cyclic multiplications of ±α for a original long multiplication, when α are different natural numbers. Two level FMT and divide multiplications are possible to reduce a memory size of a high-precision multiplication.

In this paper, I would like to present new algorithms for high-precision multiplication method. They are based on Fast Fourier Transformation (FFT) and remainder theorem. The based method is called a Fast Modulo Transformation (FMT). The FMT is composed on a primitive root of one (ω) and It is possible to define not only by a complex number but by a integer. If ω is a complex number, the computational formulation of the FMT is same as the FFT. The FMT has the wide scope about a high-precision multiplication, becouse it is based on remainder theorm. I present integer FMT, cyclic multiplications, two level FMT, direct use of complex FMT and divide multiplications for the FMT application. If α are natural numbers, I show that the FMT can achieve not only ±1 cyclic multiplication but ±α cyclic multiplications. In addition, the FMT can divide cyclic multiplications of ±α for a original long multiplication, when α are different natural numbers. Two level FMT and divide multiplications are possible to reduce a memory size of a high-precision multiplication.

収録刊行物

  • 情報処理学会論文誌

    情報処理学会論文誌 44(12), 3131-3138, 2003-12-15

    一般社団法人情報処理学会

参考文献:  7件中 1-7件 を表示

被引用文献:  1件中 1-1件 を表示

各種コード

  • NII論文ID(NAID)
    110002711651
  • NII書誌ID(NCID)
    AN00116647
  • 本文言語コード
    JPN
  • 資料種別
    Journal Article
  • ISSN
    1882-7764
  • NDL 記事登録ID
    6790741
  • NDL 雑誌分類
    ZM13(科学技術--科学技術一般--データ処理・計算機)
  • NDL 請求記号
    Z14-741
  • データ提供元
    CJP書誌  CJP引用  NDL  NII-ELS  IPSJ 
ページトップへ