No.6ベストアンサー
- 回答日時:
ANo.4の補足を拝見してようやく話が見えました。
E進数で表現した整数のかけ算をやる話ですね。結論はANo.5とほぼ同意見。ただし、繰り上がりがあるからご質問の「c」は0になるとは限らない。元のご質問に
> 畳み込み演算 h=f・g
とあったけど、この式は畳み込み演算じゃなくて、ただの整数同士のかけ算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
- 回答日時:
了解.
その h は
「多項式としての f と g の積」
そのものです.
もちろん 2つの n-1 次式の積は 2n-2次なので, 最高次 (2n-1次) の係数は必ず 0 です. なぜそんな項が含まれるかといえば, それは
「FMT の都合」
です. 原始 2n乗根を使っているので, 2n-1次まで出てきます.
「FMT」とかかっこいい名前を付けてるけど, やってることはただの FFT.
No.4
- 回答日時:
その「読んでいる資料」というのがネットワーク上にあるなら URL を出してくれると嬉しいなと思いつつ (そうじゃないなら著者とかタイトルなんかを出してもらえると探せるかもしれない),
「実はただの (多項式としての) 積」
のことを言っているのかもしれないと空想してみる.
この回答への補足
http://www.cs.t-kougei.ac.jp/nsim/method/fmtbase …
ありがとうございます。
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
- 回答日時:
あ。
ガロアの拡大体の上での剰余変換でしたか。その場合の畳み込みは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
- 回答日時:
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は変数で、
1の原始n乗根が代入されます。
次数を上げる積分の話は理解できますが、
最後がEの多項式で次数が2n-1になるには
積分範囲がEを含んでいなくてはなりません。
もちろん普通に-∞から+∞までの積分は収束しないし、
困りました。
読んでいる資料には、
定義が書いてなくて、困っています。
計算方法はあるのですが、定義がないのです。
アドバイスありがとうございます。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
- ・ゆるやかでぃべーと タイムマシンを破壊すべきか。
- ・歩いた自慢大会
- ・許せない心理テスト
- ・字面がカッコいい英単語
- ・これ何て呼びますか Part2
- ・人生で一番思い出に残ってる靴
- ・ゆるやかでぃべーと すべての高校生はアルバイトをするべきだ。
- ・初めて自分の家と他人の家が違う、と意識した時
- ・単二電池
- ・チョコミントアイス
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
以前に 「画像のローラン展開は...
-
整数問題
-
例1を組立除法でどうやってkを...
-
1/xを積分することでなぜlogxが...
-
斉次とは?(漢字と意味)
-
これがどうしても分かりません❗...
-
組立除法 1次式 ax-k の係数...
-
ax^3+bx^2+cx+d=0がα、β、γを解...
-
【降べきの順/2つの文字に着目...
-
多項式について質問です。 エク...
-
最小多項式の求めかたを教えて...
-
(x+y+2z)(2x+3y-z)(4x-y-3z)を...
-
なぜ、2変数以上の多項式を因数...
-
余次元って何?
-
F_4=Z/4Z={0,1,2,3}とする。
-
(X-a)(a+X) を展開するとど...
-
陪微分とは何ですか?
-
多項式が互いに素であると証明...
-
集合Sがディオファントス的の...
-
一般のn次既約多項式は存在する?
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
おすすめ情報