2段階FFTによる多数桁乗算

• 上位FMT(n個のI*8で1要素,全体でN要素)

P=αN/2を法とする整数FFT、αは260を利用

整数8バイト(I*8)の加減算処理(桁上げを除く)だけ

並列化はこの部分だけ。1兆桁では1要素100万桁

• 下位FMT(上位FMTの各要素別乗算に利用)

乗算結果がmod(P)を満たす負巡回FMTを利用

実か複素FMTによる多数桁乗算が現在最も高速

下位FMTはmod(P)を満たせばどのFMTでも良い

前のｽﾗｲﾄﾞ

次のｽﾗｲﾄﾞ

最初のｽﾗｲﾄﾞに戻る

ｸﾞﾗﾌｨｯｸｽの表示