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

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

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

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

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

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

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

実FFTによる多数桁乗算が現在最も高速

実FFTでは丸め誤差があり結果の整数化要　　

前のｽﾗｲﾄﾞ

次のｽﾗｲﾄﾞ

最初のｽﾗｲﾄﾞに戻る

ｸﾞﾗﾌｨｯｸｽの表示