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

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

となっているのですが、
hの次数が(2n-1)になっているのですが、
畳み込み演算はどのように定義されるのでしょうか?

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

このQ&Aに関連する最新のQ&A

eの積分」に関するQ&A: eの積分

A 回答 (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」と言えるなー。
    • good
    • 0
この回答へのお礼

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

お礼日時:2009/05/23 08:11

了解.


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

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

お礼日時:2009/05/23 08:12

その「読んでいる資料」というのがネットワーク上にあるなら 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の計算をしてみたのですがあまり高速化できませんでした。

補足日時:2009/05/22 17:51
    • good
    • 0

 あ。

ガロアの拡大体の上での剰余変換でしたか。その場合の畳み込みは
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がどこから来たかというご質問の答にはさっぱりなってませんが…
    • good
    • 0

 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を含んでいなくてはなりません。
もちろん普通に-∞から+∞までの積分は収束しないし、
困りました。
読んでいる資料には、
定義が書いてなくて、困っています。
計算方法はあるのですが、定義がないのです。

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

補足日時:2009/05/22 06:49
    • good
    • 0
    • good
    • 0
この回答へのお礼

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

お礼日時:2009/05/22 06:59

このQ&Aに関連する人気のQ&A

eの積分」に関するQ&A: e^-2xの積分

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

QM系列の生成多項式と原始多項式について

生成多項式や原始多項式に関する様々な投稿を見ましたが、
いまいち知りたいことがわからなかったので質問いたします。

周期 2^n - 1 のM系列を生成するには、{0,1}を体とする
n次の原始多項式を生成多項式として用いるということまでは
わかったのですが、このn次の原始多項式の求め方について、
いまいち理解できません。

例えば、周期 2^4 - 1 = 15のM系列を生成するには原始多項式

          x^4 + x^1 + 1 ー (1)

を用いるということですが、

            x^4 + x^2 + 1 ー (2)

ではM系列を生成できませんでした。
この2式の違いを理解していないことが原始多項式の求め方を
理解できない原因だと思うのですが、どなたかお詳しい方がいましたら、
ご教授お願いいたします。

Aベストアンサー

#1さんミスしてますので修正を。

x^4 + x^2 + 1 = (x^2 + x + 1)(x^2 - x + 1)
ですね。
念のため式変形を書くと、
x^4 + x^2 + 1 = x^4 + 2x^2 + 1 - x^2 = (x^2 + 1)^2 - x^2 = {(x^2 + 1) + x}{(x^2 + 1) - x}

だから、そもそも既約でないので、原始多項式にはなりません。
(原始多項式ならば、既約。逆は言えませんが)

しかし、単純に、原始多項式かどうかのチェックをしても、分かりますよね。

いま、数・係数としては、2で割った余りの世界(0と1からなる四則の出来る世界。色んな呼び名があるが、ここではF2と呼びます)を考えていますよね。

x^4 + x^2 + 1 でF2上の(つまり、係数が0と1からなる)多項式を割った「余り」を考えるとき、全ての多項式は、余りは3次以下の(係数が0と1からなる)式になりますよね。

係数が0と1であることから、ax^3 + bx^2 + cx + d たちは、全部で 2^4 = 16 個あるわけです。

いま、4次の原始多項式とは、xが、0を除く15個の余りを全て生成するような多項式を言います。

具体的に言うと、x , x^2 , x^3 , ・・ , x^15 を夫々割った余りがすべて異なり、0以外の全ての3次式が出てくるとき、原始多項式と言います。

ということは、もし途中で(余りとして)1がでたら、次から x , x^2 ・・と最初からの繰り返しになるので、駄目です。
よって x^15 の余りが1であり、それ以前に余り1が出てはいけません。

実は、この逆が言えて、
x , x^2 , x^3 , ・・ , x^14 の余りがすべて1でないとき(つまり x^15 ではじめて1になるとき)、(4次の)原始多項式である ・・・★

ことが言えます。

なので、(もっと良いテクニックは色々あるでしょうが)、★を満たすかどうかを、まじめに計算すれば分かります。

いま x^4 + x^2 + 1 についてやってみると、
x^4 + x^2 + 1 で割った余りは、x^4 + x^2 + 1 = 0 として、x^4 = x^2 + 1 (注:いまF2(2で割った余りの世界)上で考えているから、-1=1) を代入して次数を下げてゆけば求まりますよね。

すると、
x
x^2
x^3
x^4 = x^2 + 1
x^5 = x(x^2 + 1) = x^3 + x
x^6 = x(x^3 + x) = x^4 + x^2 = x^2 + 1 + x^2 = 1
( 2 = 0 より、2x^2 = 0 )
となり、6乗で1になってしまうので、 x^4 + x^2 + 1 は原始多項式でないと分かりますネ。

#1さんミスしてますので修正を。

x^4 + x^2 + 1 = (x^2 + x + 1)(x^2 - x + 1)
ですね。
念のため式変形を書くと、
x^4 + x^2 + 1 = x^4 + 2x^2 + 1 - x^2 = (x^2 + 1)^2 - x^2 = {(x^2 + 1) + x}{(x^2 + 1) - x}

だから、そもそも既約でないので、原始多項式にはなりません。
(原始多項式ならば、既約。逆は言えませんが)

しかし、単純に、原始多項式かどうかのチェックをしても、分かりますよね。

いま、数・係数としては、2で割った余りの世界(0と1からなる四則の出来る世界。色んな呼...続きを読む

QF_n=(a+b+c)^(2n+1)-{a^(2n+1)+b^(2n+1)+c^(2n+1)} の因数分解

F_n=(a+b+c)^(2n+1)-{a^(2n+1)+b^(2n+1)+c^(2n+1)} 
(n=1,2,3,4,5)
を因数分解せよ、という問題なのですが、どすればよいのでしょうか?

なお、答えは、

F_1=3(b+c)(c+a)(a+b)
F_2=5(b+c)(c+a)(a+b)(Σa^2+Σab)
F_3=7(b+c)(c+a)(a+b)(Σa^4+2Σa^3 b+3Σa^2 b^2+5Σa^2 bc)
F_4=3(b+c)(c+a)(a+b)(3Σa^6+9Σa^5 b+19Σa^4 b^2+35Σa^4 bc+23Σa^3 b^3+63Σa^3 b^2 c)
F_5=11(b+c)(c+a)(a+b)(Σa^8+4Σa^7 b+11Σa^6 b^2+21Σa^6 bc+9Σa^5 b^3+54Σa^5 b^2 c+23Σa^4 b^4+84Σa^4 b^3 c+123Σa^4 b^2 c^2+159Σa^3 b^3 c^2)

のようなのですが、(b+c)(c+a)(a+b)を因数に持つことは分かりますが、残りの因数はどうやってもとめるのでしょうか?

一文字を変数と見て、地道に割り算するしかないのでしょうか?
効率的な計算方法はありますでしょうか?

F_n=(a+b+c)^(2n+1)-{a^(2n+1)+b^(2n+1)+c^(2n+1)} 
(n=1,2,3,4,5)
を因数分解せよ、という問題なのですが、どすればよいのでしょうか?

なお、答えは、

F_1=3(b+c)(c+a)(a+b)
F_2=5(b+c)(c+a)(a+b)(Σa^2+Σab)
F_3=7(b+c)(c+a)(a+b)(Σa^4+2Σa^3 b+3Σa^2 b^2+5Σa^2 bc)
F_4=3(b+c)(c+a)(a+b)(3Σa^6+9Σa^5 b+19Σa^4 b^2+35Σa^4 bc+23Σa^3 b^3+63Σa^3 b^2 c)
F_5=11(b+c)(c+a)(a+b)(Σa^8+4Σa^7 b+11Σa^6 b^2+21Σa^6 bc+9Σa^5 b^3+54Σa^5 b^2 c+23Σa^4 b^4+84Σa^4 b^3 c+123Σa^4 b^2 c^2+159Σa^3 b^3 c^...続きを読む

Aベストアンサー

最後までは計算していませんが、次の方法でできそうです。
F_n = (b+c)(c+a)(a+b)(Σ[ABC] k_ABC a^A b^B c^C) とおきます。
(ここで、A+B+C = 2n+1 です。)
展開すると、F_n = (a^2 b + 略 + 2abc)(Σ[ABC] k_ABC a^A b^B c^C) です。
そして、F_n を例えば、a で A+2 回偏微分、a で B+1 回偏微分、
a で C 回偏微分、した後、a,b,c に 0 を代入します。
F_n=(a+b+c)^(2n+1)-{a^(2n+1)+b^(2n+1)+c^(2n+1)} に対しても同じようにします。
このようにすると、例えば C > 0 であれば、
k_ABC (A+2)!(B+1)!(C)! = (2n+1)! となり、係数が得られます。

Q多項式を誤解している?

多項式f(x)を求める問題で

条件の一つに

x^4f(1/x)=f(x)

をf(x)は満たすという条件がありました


n>4の範囲では右辺が多項式であるのに、左辺は多項式とならないから、矛盾する

よってf(x)の次数は4以下となる(背理法による証明)


…と模範回答にあるのですが


多項式って

例えば

f(x)=ax^4+b^3+c^2+dx+e

みたいなやつですよね?

f(x)=a/x+b+cx+dx^2+ex^3

みたいな分数型が入った式は多項式じゃないんですか?


多項式って中学生で習うのに、全然理解できてない自分にショックを受けてます。

Aベストアンサー

>f(x)=a/x+b+cx+dx^2+ex^3

みたいな分数型が入った式は多項式じゃないんですか?

そうです.多項式ではありません.
多項式はあくまでxの累乗の指数が非負整数である場合のみ指します.

ですからn>4では累乗の指数が負の整数となってしまうので多項式とは言えなくなるのでn≦4にしかなりえないということです.

Q数列{1,cos(nx)}^∞_n=1 についてのfのフーリエ級数はa_0/2+Σ[n=1..∞]a_ncos(nx) (但し,a_0=2/π∫[0..π]f(

宜しくお願い致します。

[問] (1) 数列{1,cos(nx)}^∞_n=1 は[0,π]で直交である事を示せ。
(2) f∈R[0,π](R[0,π]は[0,π]でリーマン積分可能な関数全体の集合)に対して,数列{1,cos(nx)}^∞_n=1 についてのfのフーリエ級数は
a_0/2+Σ[n=1..∞]a_ncos(nx) (但し,a_0=2/π∫[0..π]f(x)dx,a_n=2/π∫[0..π]f(x)cos(nx)dx (n=1,2,…))で与えられる事を示せ。
[(1)の解]
<1,cos(nx)>=∫[0..π]cos(nx)dx=0
次にm≠nの時,<cos(mx),cos(nx)>=∫[0..π]cos(mx)cos(nx)dx
∫[0..π]1/2{cos(mx+nx)-cos(mx-nx)}dx=0
となるので数列{1,cos(nx)}^∞_n=1 は[0,π]で直交
[(2)の解]
この関数の周期はL=π/2なので1/L∫[0..π]cos(kxπ/L)dxに代入して,
a_0=2/π∫[0..π]f(x)dx
は上手くいったのですが
a_n=2/π∫[0..π]cos(2nx)dxとなり,ここから
2/π∫[0..π]f(x)cos(nx)dxに変形できません。
どのようにして変形するのでしょうか?

宜しくお願い致します。

[問] (1) 数列{1,cos(nx)}^∞_n=1 は[0,π]で直交である事を示せ。
(2) f∈R[0,π](R[0,π]は[0,π]でリーマン積分可能な関数全体の集合)に対して,数列{1,cos(nx)}^∞_n=1 についてのfのフーリエ級数は
a_0/2+Σ[n=1..∞]a_ncos(nx) (但し,a_0=2/π∫[0..π]f(x)dx,a_n=2/π∫[0..π]f(x)cos(nx)dx (n=1,2,…))で与えられる事を示せ。
[(1)の解]
<1,cos(nx)>=∫[0..π]cos(nx)dx=0
次にm≠nの時,<cos(mx),cos(nx)>=∫[0..π]cos(mx)cos(nx)dx
∫[0..π]1/2{cos(mx+nx)-cos(mx-nx)}dx=0
となるので数列{1...続きを読む

Aベストアンサー

>この関数の周期は2L(=π)なので1/L∫[0..π]cos(kxπ/L)dxに代入したのです。
ですから、この1/L∫[0..π]cos(kxπ/L)dxがどこから出てきたのかわかりませんものね。
当たり前の公式のように書かれていますが、等式にもなっていないから何を求めているのかもわからないですし。

なので#1の回答では最終的にa_n=2/π∫[0..π]f(x)cos(nx)dxになるような式を予想して解説しました。

>これはfは周期2πの偶関数という意味ですよね。
>今,fは周期はπだと思うのですが…
>あと,どうしてfは偶関数だと分かるのでしょうか?
質問の文に
『数列{1,cos(nx)}^∞_n=1 についてのfのフーリエ級数は
a_0/2+Σ[n=1..∞]a_ncos(nx) (但し,a_0=2/π∫[0..π]f(x)dx,a_n=2/π∫[0..π]f(x)cos(nx)dx (n=1,2,…))で与えられる事を示せ。』
とあったのでf(x)=a_0/2+Σ[n=1..∞]a_ncos(nx)と表せる前提で話をして良いのかなと思ったのです。
また、f∈R[0,π]の関数を周期[-π,π]で展開することも可能なので一概に周期[0,π]とも言えないと思うのです。
(ただし、その場合にも偶関数として展開、奇関数として展開などの適当な前提は要りますが)


どうやら私が質問や問題の内容を推測して回答してしまったのがよくなかったようですね。
今回は補足要求と言うことにしておきます。

・今回の問題(2)の題意は
  fがa_0/2+Σ[n=1..∞]a_ncos(nx)で書けることを示すことですか?
それとも
  f(x)=a_0/2+Σ[n=1..∞]a_ncos(nx)とするとa_0=2/π∫[0..π]f(x)dx,a_n=2/π∫[0..π]f(x)cos(nx)dxとなることを示すことですか?

・『数列{1,cos(nx)}^∞_n=1 についてのfのフーリエ級数』とはこの場合どういう意味でしょう?把握してらっしゃいますか?

・fを展開する際の周期ですが本当に[0,π]ですか?
[0,π]ではcos(nx)とsin(mx)が直交しないですし、
f(x)=Σ{b_n*sin(nx)}と奇関数として展開するしか出来ない気がするんですが。

>この関数の周期は2L(=π)なので1/L∫[0..π]cos(kxπ/L)dxに代入したのです。
ですから、この1/L∫[0..π]cos(kxπ/L)dxがどこから出てきたのかわかりませんものね。
当たり前の公式のように書かれていますが、等式にもなっていないから何を求めているのかもわからないですし。

なので#1の回答では最終的にa_n=2/π∫[0..π]f(x)cos(nx)dxになるような式を予想して解説しました。

>これはfは周期2πの偶関数という意味ですよね。
>今,fは周期はπだと思うのですが…
>あと,どうしてfは偶関数だと分かるのでし...続きを読む

Qべき乗表現と多項式表現

すいません。
べき乗表現と多項式表現の関係がわかりません。
例えば
0000 -> 0(べき乗) -> 0(多項式),
0001 -> 1(べき乗) -> 1(多項式),
0010 -> α(べき乗) -> α(多項式),
0011 -> α~2(べき乗) -> α~2(多項式),
0100 -> α^3(べき乗) -> α~3(多項式),
0101 -> α~4(べき乗) -> α~3+1(多項式),

ここでなぜ、0101がα~3+1になるのでしょう?
であれば、0011はα+1ではないのでしょうか?
また、さらに0110がα~5(べき乗)の時、
なぜ、α~3+α+1になるのでしょう?

理屈を教えてください。

Aベストアンサー

有限体の拡大理論の話です。情報理論系の本を参照されるのが一番とは思いますが。

まずすべて3次以下の多項式表現を考えていること、4桁の2進数を考えていることは
次の方程式:x^4+x+1=0をZ/2Z={0,1}上で考えていることから来ています。
つまりZ/2Z上の多項式環を既約多項式x^4+x+1で割った4次の拡大体を考えるのです。

演算は普通にZ/2Z上の多項式環の演算ですが、x^4+x+1=0という約束がありますから、
かならず3次以下の多項式に変形することができます。
もう少し詳しく言うと、Z/2Zの4次拡大体をGF(2^4)と書くとき、
GF(2^4)の元は3次以下の多項式16個、
0,1,α,α+1,α^2,α^2+1,α^2+α,α^2+α+1,
α^3,α^3+1,α^3+α,,α^3+α+1,α^3+α^2,α^3+α^2+1,α^3+α^2+α,α^3+α^2+α+1
からなる体のことです。

さてべき乗表現と多項式表現の対応を見るには、x^4+x+1=0に気をつけるだけです。
3次以下の多項式はそのままですから放置して、
0101 -> α^4=-α-1=α+1
となります。Z/2Zなので-1=1に注意してください。同様に、
0110 -> α^5=-α^2-α=α^2+α
0111 -> α^6=-α^3-α^2=α^3+α^2
1000 -> α^7=-α^4-α^3=α^4+α^3=(α+1)+α^3=α^3+α+1
などとなります。α^15まで計算すると上の3次以下の多項式がすべて
出てくることに確認してみてください。

なお大事な注意ですが、多項式表現は別の既約多項式を用いて
表すと異なる表示になりうることです。
大抵x^n+x+1のタイプの多項式は既約になるのでこれを用いる
ことが多いのではないかと思われます。
詳しいことは僕は知らないので調べてください。

それから二進表記のまま通常の演算を考えると頭が混乱するので
避けてください。
あくまでべき乗表現、あるいは多項式表現で演算を考えるべきです。
べき乗表現は積の計算に大変便利な表記で、たとえば
α^4×α^3=α^7
などとなります。多項式表現のまま積の計算も出来ますが、
多項式表現はどちらかというと和の計算に便利です。
Z/2Z上で考えているので、2=0に注意して、たとえば
(α^3+α+1)+(α^3+α^2+1)=α^2+α
といった感じです。

検索では下記ページぐらいしか見つけられませんでしたが、
参考にはなるかと思います。

参考URL:http://www.ccad.sccs.chukyo-u.ac.jp/~mito/syllabi/daisu/fext/index.htm

有限体の拡大理論の話です。情報理論系の本を参照されるのが一番とは思いますが。

まずすべて3次以下の多項式表現を考えていること、4桁の2進数を考えていることは
次の方程式:x^4+x+1=0をZ/2Z={0,1}上で考えていることから来ています。
つまりZ/2Z上の多項式環を既約多項式x^4+x+1で割った4次の拡大体を考えるのです。

演算は普通にZ/2Z上の多項式環の演算ですが、x^4+x+1=0という約束がありますから、
かならず3次以下の多項式に変形することができます。
もう少し詳しく言うと、Z/2Zの4次拡大体をGF...続きを読む

Qx^n-y^n=(x-y)(x^n-1+x^n-2y+x^n-3y^2

x^n-y^n=(x-y)(x^n-1+x^n-2y+x^n-3y^2+・・・+y^n-1)
となるのはなぜですか?
教えてください。

Aベストアンサー

1+r+r^2+・・・+r^(n-1)=(1-r^n)/(1-r)

r=x/yとおくと

1+(x/y)+(x/y)^2+・・・+(x/y)^(n-1)={1-(x/y)^n}/{1-(x/y)}
故に、
{1-(x/y)^n}={1-(x/y)}{1+(x/y)+(x/y)^2+・・・+(x/y)^(n-1)}

両辺にy^nを乗じて
x^n-y^n=(x-y)(x^n-1+x^n-2y+x^n-3y^2+・・・+y^n-1)

Q同次多項式について

同次多項式における定理、
  同次多項式f(x,y,z)の因子は、また同次多項式である
の証明をわかりやすくおしえてもらいたいのですが・・・
  よろしくお願いします。

Aベストアンサー

定理かどうかは知りませんが、簡単に証明できますよ。
一般的に次のように言い換えて証明します。

「体K上の同次多項式 f(x_1,・・・,x_n) の因子は、
また体K上の同次多項式である」

質問については n=3で係数が整数(有理数)の場合であるため
上記証明に包含されます。
とりあえず、環、整域、体とか言う言葉を知っていますよね?
知らない場合はわかりやすくないので(^^A
イメージだけつかんでください。

(proof)
背理法による:

f(x_1,・・・,x_n) が K上既約多項式ならば、
因子は定数か自身の定数倍であるため明らか。
したがってK上可約としてよい。

このときfの同次でない因子をgの存在を仮定する。
fは可約より
f(x_1,・・・,x_n) = g(x_1,・・・,x_n)q(x_1,・・・,x_n)
とあらわせる。(剰余定理)
ここで
gの最大項の次数をK,最小項の次数をk
qの最大項の次数をL,最小項の次数をl
とすると、右辺の次数は最大L+K,最小l+kであるが
gは同次でないのでL+K != l+k
これはfが同次であることに反する。

※同次多項式とは、各項の次数がすべて等しい多項式である。
例 f(x,y) = x^2 + 7xy + y^2(2次で同次)
f(x,y,z) = x^3 + 3xyz + y^3 + x^2y (3次で同次)
f(x,y) = x^2 + y+ 3 (同次でない)

※因子とは、整数でいう約数。体(整域)上で定義される。
※既約多項式とは、整数でいう素数。体(整域)上で定義される。

定理かどうかは知りませんが、簡単に証明できますよ。
一般的に次のように言い換えて証明します。

「体K上の同次多項式 f(x_1,・・・,x_n) の因子は、
また体K上の同次多項式である」

質問については n=3で係数が整数(有理数)の場合であるため
上記証明に包含されます。
とりあえず、環、整域、体とか言う言葉を知っていますよね?
知らない場合はわかりやすくないので(^^A
イメージだけつかんでください。

(proof)
背理法による:

f(x_1,・・・,x_n) が K上既約多項式...続きを読む

Q(1+h)^n≧1+nh+{n(n-1)/2}h^2

h>0のとき(1+h)^n≧1+nh+{n(n-1)/2}h^2

これを示すのに「右辺は二項定理で展開して昇べき順で並べたときの最初の3項」ってことでは証明になりませんか?
数学的帰納法でしょうか?

あと、0<x<1のときlim[n→∞]nx^n=0
を先の不等式を用いて示せという問題がわかりません。
一見明らかにみえますけど。

Aベストアンサー

この問題の重点は後半にありそれのヒントが前半です。
後半は
∞*0
の形の極限ですから明らかではすみません。
n乗の収束の方が速いとわかっていれば明らかですけど。

二項定理ぐらい使ってもいいと思います。
それさえも証明しなければいけないとしたら
どんなことでも最初から証明を始めなければいけないことになります。

二項定理の証明は数学的帰納法とは限りません。

Q多項式の定義について

「X~2+2√x+1、は多項式ではない」と参考書に載っていたのですが、なぜ多項式ではないのでしょうか。項が複数あるので多項式だと思うのですが。
宜しくお願いします。

Aベストアンサー

> 項が複数あるので多項式だと思うのですが。
正確に言うと、「単項式」が複数ある(加算、減算されている)場合に多項式と呼びます。

変数xの単項式は、
ax^n (a: 定数, n: 0以上の整数)
で表されます。

質問で挙げられた式は、2√xが 2√x = 2x^1/2 ですので単項式ではなく、そのため式全体は多項式ではないと言えます。

Q極限値lim[n→∞](3^n/(2^n+n^2))とlim[n→∞](2^n+3^n)^(1/n)の求め方は?

(1)lim[n→∞](3^n/(2^n+n^2))
(2)lim[n→∞](2^n+3^n)^(1/n)

の極限値がわかりません。
(1)は3^nで分母・分子を割って
lim[n→∞](3^n/(2^n+n^2))
=
lim[n→∞][1/{(2/3)^n+n^2/3^n}]
までいけたのですがn^2/3^nが収束するのか発散するのか分かりません。
どうなるのでしょうか?

あと、(2)は対数を取って
lim[n→∞]log(2^n+3^n)^(1/n)
=
lim[n→∞](1/n)log(2^n+3^n)
までいけたのですがここから先へ進めません。

Aベストアンサー

YYoshikawaさん、こんにちは。

[(1)について]

> n^2/3^nが収束するのか発散するのか分かりません。

まず感覚として、ANo.1さんも書かれているように、n=100で考えてみると、
 n^2/3^n = 10000/3^100
ですが、3^2=9 が大体10ですから、3^100 は、10^50 ぐらいなわけで、0が50個ぐらいつきますから、10000などよりは、はるかに大きくなります。つまり n^2/3^n → 0 が予想できます。

数式では次のように証明できます。

まず、n^2/3^n はnが大きいとき単調減少です。
実際、a(n)=n^2/3^n とおき、

 a(n+1)/a(n) = [(n+1)^2/3^(n+1)]/[n^2/3^n]

と比をとってみると、

 a(n+1)/a(n) = [1+(1/n)]^2/3 = [1 + 2/n + 1/n^2]/3 … (3)

ですが、nが大きいときには、2/n < 1, 1/n^2 < 1 なので、(3)は、

 a(n+1)/a(n) < 1

となり、単調に減少することがわかります。
まずこの時点で発散はしないことがわかります。
また、a(n) > 0 なので、lim_{n→∞} a(n) ≧ 0 となります。

もし、a(n) の収束値bが、正の有限値なら、n→∞で、
 a(2n)/a(n) → b/b = 1
になるはずですが、
 a(2n)/a(n) = [(2n)^2/3^{2n}]/[n^2/3^n] = 4/3^n → 0
になるので、収束値bは正の有限値にはなりません。

従って、
 lim_{n→∞} a(n) = 0 … (4)
が得られます。

[(4)の別証]
(3)式 a(n+1)/a(n) = [1+(1/n)]^2/3 = [1 + 2/n + 1/n^2]/3 より、
n>10で、
 a(n+1)/a(n) < [1 + 2/10 + 1/100]/3 < 2/3
故に、n→∞ のとき、
 0 < a(n) = [a(n)/a(n-1)]・[a(n-1)/a(n-2)] ・…・ [a(12)/a(11)]・a(11)
      < (2/3)^{n-11}× a(11) = (2/3)^n × (3/2)^{11}a(11) → 0
故に
 lim_{n→∞} a(n) = 0
が得られる。
(別証終わり)


[(2)について]

まず感覚的なことを説明しますと、nが大きいとき、2^nは3^nに比べてはるかに小さくなるので、基本的に、lim[n→∞](2^n+3^n)^(1/n)の、2^n+3^nの部分は3^nに近づくことがわかり、問題の式は(3^n)^{1/n}=3 になることが予想されます。

これを式で言うには、対数をとるより、

 lim_{n→∞} [3^n×{1+(2/3)^n}]^{1/n}
 = lim_{n→∞} 3×[1+(2/3)^n]^{1/n} … (5)

と変形するのが良いでしょう。(2/3)^n → 0 なので、
 [1+(2/3)^n]^{1/n} → 1 … (6)
なので、
 (5) = 3
になります。


なお、(6)が明らかと思われない場合は、
 1 = 1^{1/n} < [1+(2/3)^n]^{1/n} < 1+(2/3)^n → 1
(∵ a > 1 に対して、a^{1/n} = (a^{1/n})^n = a )
より、[1+(2/3)^n]^{1/n} → 1
と証明します。

YYoshikawaさん、こんにちは。

[(1)について]

> n^2/3^nが収束するのか発散するのか分かりません。

まず感覚として、ANo.1さんも書かれているように、n=100で考えてみると、
 n^2/3^n = 10000/3^100
ですが、3^2=9 が大体10ですから、3^100 は、10^50 ぐらいなわけで、0が50個ぐらいつきますから、10000などよりは、はるかに大きくなります。つまり n^2/3^n → 0 が予想できます。

数式では次のように証明できます。

まず、n^2/3^n はnが大きいとき単調減少です。
実際、a(n)=n^2/3^n とおき、...続きを読む


人気Q&Aランキング

おすすめ情報