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で質問しましょう!
似たような質問が見つかりました
- 数学 場合によって計算が変わる数列について。 4 2023/04/20 18:24
- 法学 株式会社が設立の登記をする場合において、その定款に設立費用にかかる定めがある場合、 5 2022/12/17 05:41
- システム CPUの問題について 2 2022/07/09 12:04
- Excel(エクセル) バイナリー演算を勉強したい 1 2023/04/19 14:17
- 照明・ライト シーリングライト選びで迷っていて… リビング全体は18畳なのですが、ダイニング側に一つとキッチンに埋 3 2022/11/09 21:07
- 一戸建て 注文住宅の総費用について 2 2022/08/13 17:12
- その他(パソコン・スマホ・電化製品) FLIP5x2発 vs CHARGE5 1 2023/03/30 23:29
- ガーデニング・家庭菜園 茗荷の植え替えについて 4 2022/12/31 19:58
- 数学 群の公理 xの逆元yはxごとにただ1つ決まる。そこで そのyを、一般的には記号x'で表す。 この演算 2 2022/08/06 02:23
- DIY・エクステリア DIY得意な方へ。折りたたみ台車の案をください。 4 2022/06/23 09:56
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
e^sinXの展開式について。。。
-
斉次とは?(漢字と意味)
-
データのノイズ除去法 - Savitz...
-
約数と因数の違い
-
(x-1)(x-2)(x-3)の展開の...
-
多項式について質問です。 エク...
-
arcsinのマクローリン展開について
-
問題が理解できません
-
組立除法 1次式 ax-k の係数...
-
三乗根を含んだ最小多項式
-
約数と因数の違い(∈N)
-
フルビッツの安定判別法
-
a~2+2a+1の因数は[a+1]だけで...
-
deg f?
-
基本対称式ってなんでしょうか?
-
(X-a)(a+X) を展開するとど...
-
数学 有理式 無理式
-
中三数学 (-5X+1)(5X+1)の答...
-
調和多項式について
-
エルミート補間について
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
多項式について質問です。 エク...
-
単項式と分数式の違いについて
-
斉次とは?(漢字と意味)
-
データのノイズ除去法 - Savitz...
-
阪大2014年数学挑戦枠2問からで...
-
余次元って何?
-
(x-1)(x-2)(x-3)の展開の...
-
数学 因数分解 X^3+x^2+x−1 ...
-
(x+y+2z)(2x+3y-z)(4x-y-3z)を...
-
約数と因数の違い(∈N)
-
数を拡張するとはなんですか? ...
-
等差×等比 型の数列の和を求め...
-
arcsinのマクローリン展開について
-
ローラン展開についてです。
-
CRCのアルゴリズムって、どんな...
-
なぜ、2変数以上の多項式を因数...
-
deg f?
-
0は偶関数?
-
原始多項式の求め方
-
テイラー展開の剰余項
おすすめ情報