多項式の畳み込み演算

質問

FMTについて調べています。
二つの多項式の畳み込み演算が分かりません。

f=aE^(n-1) + ...
g=bE^(n-1) + ...
この畳み込み演算　h=f・ｇ
とすると、
h=cE^(2n-1) + ...

となっているのですが、
ｈの次数が（２ｎ－１）になっているのですが、
畳み込み演算はどのように定義されるのでしょうか？

お分かりの方よろしくお願いします。

回答No.6

stomachman · ベストアンサー

ANo.4の補足を拝見してようやく話が見えました。E進数で表現した整数のかけ算をやる話ですね。結論はANo.5とほぼ同意見。ただし、繰り上がりがあるからご質問の「c」は0になるとは限らない。

　元のご質問に

> 畳み込み演算　h=f・ｇ

とあったけど、この式は畳み込み演算じゃなくて、ただの整数同士のかけ算fgです。
　ところが、整数fとgのかけ算ってのは、fとgをE進数表現したときの各桁ごとの計算方法を見ると畳み込みにそっくりである。つまり、fとgをE進数表現したもの（だからEの多項式の形になる）において、各桁（つまり多項式の係数）だけを並べた2n個の要素を持つ列を
u=<0,...,0,a[n-1],...,a[0]>
v=<0,...,0,b[n-1],...,b[0]>
とすると、積fgをEの多項式で表したものの係数cは、u,vの畳み込み
c[j]=Σu[k]v[j-k]
になる。（ただし積fgをE進数表現にするには、繰り上がりの処理が必要。筆算でやるかけ算と全く同じ事です。）なので、どうやら、「整数同士のかけ算」と「E進数の各桁の畳み込み」を区別しないで言ってるらしい。
　さて、その畳み込みをまともにやったら大変（n^2のオーダの計算量が掛かる）なんで、まずはf,gをFMTしておいて、convolution定理によって（沢山の、桁数のごく小さい）かけ算に変換して実行するというのが話の本筋。（convolution定理を使うにはFFT(Fast Fourier Transform)をやってもいいんだけど、丸め誤差が出るのがいやらしい。FMTなら誤差の心配がない。）

> 定義は別にあるが、でも上の方法で求まるよ

　いやいや、おそらく引用資料の3.2と3.3が「Modulo Transform」なるものの定義でしょう。ANo.3に書いた変換は（昔から）Finite Field Transformと呼ばれている。これを少し改変してE進数の各桁に適用したものを特に「Modulo Transform」と名付けたんでしょうね。
　しかし実際の計算はFFT(Fast Fourier Transform)と全く同じ形にバタフライ演算を組み合わせたもので行います。そうしないとちっともfast (n log(n)のオーダー）にならない。（このことは、同じ資料のどこかのページか参考文献に書いてあるんじゃなかろうか。）かくて、ANo.5にあるとおり、「やってることはただのFFT」と言えるなー。

お礼

分かりました。
自分で定義や桁上がりの分を整理した書き直してから
プログラムを組むかどうか決めます。
ありがとうございました。

回答No.5

Tacosan

了解.
その h は
「多項式としての f と g の積」
そのものです.
もちろん 2つの n-1 次式の積は 2n-2次なので, 最高次 (2n-1次) の係数は必ず 0 です. なぜそんな項が含まれるかといえば, それは
「FMT の都合」
です. 原始 2n乗根を使っているので, 2n-1次まで出てきます.
「FMT」とかかっこいい名前を付けてるけど, やってることはただの FFT.

お礼

分かりました。
自分で定義や桁上がりの分を整理した書き直してから
プログラムを組むかどうか決めます。
ありがとうございました。

回答No.4

Tacosan

その「読んでいる資料」というのがネットワーク上にあるなら URL を出してくれると嬉しいなと思いつつ (そうじゃないなら著者とかタイトルなんかを出してもらえると探せるかもしれない),
「実はただの (多項式としての) 積」
のことを言っているのかもしれないと空想してみる.

補足

http://www.cs.t-kougei.ac.jp/nsim/method/fmtbase.htm
ありがとうございます。
URLは、上のものです。

この中の

4. 畳込み演算への適用方法
　　記号Eに関するn-1次の2個の関数f,gから畳込み演算で2n-1次の関数hの各係数ckを
　求める方法を述べる。
　　　f = an-1En-1 + …… + a1E + a0 , 　　g = bn-1En-1 + …… + b1E + b0　　- - - (5)
　　　h = f ・ g = c2n-1E2n-1 + c2n-2E2n-2 + …… + c1E + a0　　　　　　　　　　- - - (6)
　関数hの各係数ckは下記3種類の変換を順に行って求める。
　(1) FMT順変換
　　　(5)式のf,gにFMT変換に原始2n乗根ωを用いて(3)式に従いFMT順変換を行い、下記の
　　各2n個の係数fk,gkを求める。
　　　　fk = mod( f, E - ωk) = a2n-1ω(2n-1) k + a2n-2ω(2n-2) k + …… + a1ωk + a0
　　　　gk = mod( g, E - ωk) = b2n-1ω(2n-1) k + b2n-2ω(2n-2) k + …… + b1ωk + b0　
　　　　　　k = 0, 1, …… , 2n-1　　　　　　　　 　　　　　　　　　　　　　　　　　　- - - (7)
　(2) 項別乗算
　　　(7)式のfk,gkを対応する項別に乗算して、下記のhk を求める。
　　　　hk = fk ・ gk 　　　　　　k = 0, 1, …… , 2n-1　　　　　　　　　　　　　　　- - - (8)
　　ここで、hk = mod(h , E - ωk )なる関係がある。
　(3) FMT逆変換
　 　　hk = mod(h , E - ωk )なる関係を利用して、FMT逆変換で(8)式で 求めたhk から
　　Eに関する2n-1次の関数hの2n個の係数cjを(4)式に従い下記で求める。
　　　cj = ( f2n-1ω-(2n-1) j + f2n-2ω-(2n-2) j + …… + f1ω-j + f0 ) / ( 2n )
　　　　　　j = 0, 1, …… , 2n-1　　　　　　　　 　　
の部分ですが、
これが定義なのでしょうか？
文章が、
次のように定義される
ではなく
求める方法。。。
となっているので、
定義は別にあるが、でも上の方法で求まるよ
といっているように理解したのですが
誤解だったのでしょうか？
これを、RSA暗号の計算に使いたいのです。
以前、FFTでRSAの計算をしてみたのですがあまり高速化できませんでした。

回答No.3

stomachman

あ。ガロアの拡大体の上での剰余変換でしたか。その場合の畳み込みは
H(j)=ΣF(k)G(k-j) (Σはk=0～N-1についての総和）
に違いありません。これを、剰余付きの和と積を使った
H*(j) ≡ ΣF(k)G(k-j)
に置き換えても、もしHがオーバーフローする （拡大体からはみ出してしまう）ことがないのであれば、
H*(j) = H(j)
となって、（FFTと違って丸め誤差なしに）畳み込みができたことになる。その代わり、剰余の計算が結構な手間です。（大昔に使ってみたことがあるけれども、多分、計算の規模が小さすぎたのでしょう、FFTに比べてさしてメリットが出ず、こりゃ駄目だと諦めたんでした。）
　この場合、原子根E(n)は、FFTにおける指数関数e(2πn/N)と同じ働きをします。e^(2πN/N)=1となるのと同じく E^N ≡ 1となるからです。そして、
f(n) = FMT(F) ≡ ΣF(k)E^(nk)
g(n) = FMT(G)
h(n) = FMT(H)
のとき、コンボルーション定理
h(n) ≡ f(n)g(n)
が成り立つ。おそらく、ご検討なさっているのはこの定理の証明の途中経過か、あるいはFMTの計算の途中経過なのではないか。だとすると、f, gの逆FMT変換F, Gが、本来畳み込みをやろうとする対象の関数だと思われます。
　2n-1がどこから来たかというご質問の答にはさっぱりなってませんが…

回答No.2

stomachman

FMTが何なのか分かりませんが、多項式とある以上、ご質問はEが実数の変数、nは定数で自然数n≧1ってことですかね。だとすれば、
f(E)=aE^(n-1)+ u(E)　　ただしa≠0、u(E)はEのn-2次以下の多項式
g(E)=bE^(n-1)+ v(E)　　ただしb≠0、v(E)はEのn-2次以下の多項式
の畳み込みは
h(E)=∫f(x)g(E-x)dx (積分はx=p～qの定積分）
であって(p,qはご質問からだけでは分からない）、従って
h(E)=ab∫(x^(n-1)+s(x))((E-x)^(n-1)+t(E-x))dx
である。積分の中身である多項式のxの最高次数は2n-2ですから、積分すればxの2n-1次の多項式になるんだけれども、Eの多項式と見たときには次数はn-1のまんまです。話が合いません。

　ってことはひょっとして、Eは実は定数であって、pかqがEの1次式になってるんじゃなかろうか。たとえば
f(t)=at^(n-1)+ u(t)　　ただしa≠0、u(t)はtのn-2次以下の多項式
g(t)=bt^(n-1)+ v(t)　　ただしb≠0、v(t)はtのn-2次以下の多項式
h(t)=∫f(x)g(t-x)dx (積分はx=p～Eの定積分）
が本来の話であるとするならば、h(E)は不定積分の結果（xの2n-1次の多項式）にx=Eを代入したものとx=qを代入したものの差、つまり、Eの2n-1次多項式ということになる。これなら一応辻褄が合います。

補足

FMTは高速剰余変換
のことです。
Eは変数で、
１の原始ｎ乗根が代入されます。
次数を上げる積分の話は理解できますが、
最後がEの多項式で次数が２ｎ-1になるには
積分範囲がEを含んでいなくてはなりません。
もちろん普通に－∞から+∞までの積分は収束しないし、
困りました。
読んでいる資料には、
定義が書いてなくて、困っています。
計算方法はあるのですが、定義がないのです。

アドバイスありがとうございます。

回答No.1

rabbit_cat

http://ja.wikipedia.org/wiki/%E7%95%B3%E3%81%BF%E8%BE%BC%E3%81%BF

お礼

ありがとうございます。
このページのものとは
違う意味だと思います。