混合基数FFTの実装上の問題

前回、混合基数（Nが素因数に分解できる場合）のFFTアルゴリズムを整理した。2のベキのアルゴリズムを一般化してできるということがわかった。
でも2のベキとは違う難しさがある。

並び替えの問題

ここまではいい。問題は並び替え。2の基数の場合はビット逆順という面倒だけど比較的簡単な方法があった。混合基数の場合にも全く同じことをすればいい。つまり基数が3なら3進法で表してそれを逆から読めばいい。しかし、素因数分解の結果例えば2×3×5×7×11（=2310）なんて場合もあるかもしれない。この並び替えを一般的に行うアルゴリズムはどうすればいいんだ？FFTの分解の順序にも依存するし。

どうすればいいのか全然思いつかないので、それぞれのステップで中間結果を保持してそれぞれで並び替えることにする。Nがm個の素数に素因数分解されたとすると一番簡単な方法だとN×m個分の中間結果保持バッファが必要になってしまう。

とりあえずそれで実装して問題が出たり、何かいい方法を思いついたら考え直すことにする。

素因数分解

混合基数を扱うためには与えられたNを素因数分解する必要がある。素因数分解も暗号の分野では中心的な話題で、RSA暗号などの基礎となる部分は効率的なアルゴリズムがないことを前提にしている。

素因数分解の一番プリミティブな方法は2から始めて√Nまでの素数で割ってみる、という方法。素因数分解は基本的にはこの方法しかない。

とはいうものの頭のいい人はいっぱいいるもんで、FFTほど劇的ではないにしてもただ順番に割ってみる、というのよりはいい方法をいろいろ考えだしている。ポラード・ローアルゴリズムなど、いろいろあるけどどうも僕にはピンとこない。どうしても頭が数論用にできていない。

今回は、暗号で使うような巨大な整数の素因数分解をしたいわけではないので一番素朴な方法でやろうとおもう。それでも√Nまでの素数は必要で、それを生成するためのアルゴリズムも必要になるが、今回FFTは2次元で、無制限に大きいデータは使わないので、はじめから素数列をハードコードしてしまおう。迷路を作るのに10000×10000の広さのデータを使うことはないだろうから、100までの素数があれば十分だろう。

こないだのUIではどこにも制限がかからないので、サイズを決めるときにある大きさ以上を入力しようとしたらダイアログを出して訂正してもらうようにしよう。