著者

後 保範

出版者

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

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.44, no.12, pp.3131-3138, 2003-12-15

被引用文献数

1

---

多数桁乗算に関する計算アルゴリズムを提案する.そのアルゴリズムは高速フーリエ変換(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.