- ベストアンサー
[情報セキュリティ]以下のシェアから秘密ｓを求めよ
問題． (2,3)-しきい値法において、ラグランジュの補間公式を用いて、以下のシェアから秘密ｓを求めよ t1=f(1)=2 t3=f(3)=4 解答. i1 = 1, i2 = 3とする λ1(0) = -i2/(i1 - i2) = -3/(1-3) = 3/2 λ2(0) = -i1/(i2 - i1) = -1/(3-1) = -1/2 s = f(0) =λ1(0) f(i1) + λ2(0) f(i2) =(3/2)・２＋（-1/2）・４ ＝１ ー－－講義資料ー－－ (2,3)-しきい値法の例． 秘密s=1, a1=1とする f(x)=1+xとなる よってf(0)=s シェア t1=f(1)=2 t2=f(2)=3 t3=f(3)=4 ラグランジュの補間公式． ｛f(i1), ・・・,f(ik)｝からf(x)を補間する公式 f(x)=λ1 f(i1)+λk f(ik) mod p s=f(0)=λ1(0) f(i1)+・・・+λk(0) f(ik) mod p ー－－－ 全くわかりません
- qwsfgh
- お礼率30% (17/56)
- その他([技術者向] コンピューター)
- 回答数1
- ありがとう数1
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
このようにシェアが2つ与えられているときは，点(1,2)と点(3,4)を通る直線のy切片を求めればよい。 点(1,2)と点(3,4)を通る直線というのはy=x+1だから秘密s=f(0)=1 シェアが3つのときは，その3点を通る2次関数のy切片を求める。 シェアが4つのときは，その4点を通る3次関数のy切片を求める。 ラグランジュの補間公式というのは(n+1)個の点を通るn次関数を求める公式です。
関連するQ&A
- 大学数学の問題です
勉強不足でわかりません。得意な方、解答お願いいたします。 問１ 補間点をX0=1,X1=2,X2=3,とし、これらの補間点での関数値をf0=4, f1=-3, f2=2とする。ラグランジュ補間多項式をP(X)＝A(x-2)(x-3)+B(x-1)(x-3)+C(x-1)(x-2)と表したとき、A,B,Cに入る値を求めよ。 問2 関数f(x)=x^3-1に対するニュートン法の式をｘk+1＝ｘk－Aとする。Aを書き表せ。※k+1、kは1/4下付文字 問３ n=4としてa1=2、a2=3、a3=-2、a4=5が与えられたとき、以下の疑似コードを実行するとa1,a2,a3,a4はどうなるか。 for i =1,2,…,n-1 do if ai＜ai+1 then t ← ai+1 ai+1 ← ai ai+1 ← ｔ end if end for ※疑似コードのi、i+1は1/4下付文字
- 締切済み
- 数学・算数
- ラグランジュ補間多項式
何回でも微分できる関数f(x)とし、 x0,x1,x2,x3,x4を刻幅hの等間隔分点としたとき(xk=x0+kh) f(x)のラグランジュ補間p4(x)を求めて ∫[x0,x4]p4(x)dx = 2h/45(7f(x0)+32f(x1)+12f(x2)+32f(x3)+7f(x4)) となることを示したいのですが p4(x)を求めて積分しようと思っているのですが p4(x)の式がラグランジュ補間のとおりにやるとすごく長い式になってしまし 積分するにあたって多項式の形にしようとしてるのですがよくできません 教えてください。
- ベストアンサー
- 数学・算数
- 実数s>0,t>0で、s^2+t^2=1を満たすとき、
実数s>0,t>0で、s^2+t^2=1を満たすとき、 x^4-2(s+t)x^2+(s-t)^2=0 の解の取り得る範囲を求めよ。 次のように考えました。正しいでしょうか s+t=kとおくと、2st=k^2-1 また、実数s>0,t>0で、s^2+t^2=1のとき、 1<=k<=√2 与式は x^4-2kx+2-k^2=0 これより、k^2+2x^2k-x^4-2=0 これが、1<=k<=√2の範囲に解を持つ条件は、 f(k)=k^2+2x^2k-x^4-2とおくと f(1)<=0かつf(√2)=>0 これより、x^2(x^2-√2)=>0 よって、x=0,x<=-2^(3/4),2^(3/4)<=x よろしくお願いします。
- ベストアンサー
- 数学・算数
- 任意のkに対し、f(m）がk個の素因数を持つ様なm
f(x)を整数係数のmonic polynomialとしたとき 任意の整数kに対して、f(m)がk個の異なる素因数をもつような整数mは存在するか という問題なのですが、 素数を小さい順にp_1 ,p_2, p_3, ...とし、 f(m)の素因数がp_1, p_2, ... , p_kとなるようなmが存在することを示す。 f(x)は問題文の条件より f(x)=(x-a_1)(x-a_2)....(x-a_n)とおける (a_iは整数） p_iは素数なので互いに素 中国の剰余定理より y≡a_1 (mod p_1) y≡a_2 (mod p_2) y≡a_3 (mod p_3) ... y≡a_k (mod p_k) を満たすｙが存在する。 y-a_1≡0 (mod p_1) y-a_2≡0 (mod p_2) y-a_3≡0(mod p_3) ... y-a_k≡0(mod p_k) となるためf(y)はp_1, p_2, ..., p_kのすべてで割り切れる。 間違いがあったら指摘ください。
- ベストアンサー
- 数学・算数
- 三次補間を使った近似値の求め方
三次補間でf(x) = sinh(x)の近似を求めたいです。 f(0) = 0.0000、f(1) = 1.1752 f′(0) = 1.0000 、f′(1) = 1.15431 の値が与えられている状態です。 この場合、f(0.5)は三次補間(cubic interpolation)の求め方はこれで正しいのでしょうか？ p(x_i) = y_iとp(x_i + h) = y_i + h*y_i'より f(0.5) = f(0+0.5) = y_0 + (0.5)*y_0' = 0.000 + 0.5*1.000 = 0.5 よってf(0.5) = 0.5 補間の手法が沢山あって少しこんがらがっています。 ただ、sinh(0.5) =0.522・・・なので有っていそうなのですが 間違っていたら教えてください＞＜お願いします＞＜
- ベストアンサー
- 数学・算数
- 数学、ｍｏｄ ｐのｋ乗
ｘの２乗≡ａ（ｍｏｄ ｐのｋ乗）が整数解を持てばｘの２乗≡ａ（ｍｏｄ ｐのｋ＋１乗）も整数解を持つ ｐは素数、ｋは０以上の整数、ａは整数 この証明についての質問です。 ｘの２乗≡ａ（ｍｏｄ ｐのｋ乗）の整数解をｘ１とすると ｘ１の２乗－ａ＝（ｐのｋ乗）ｓ ｓは整数 ｘ２＝ｘ１＋（ｐのｋ乗）ｔとおくと ｘ２の２乗－ａ＝（ｘ１＋（ｐのｋ乗）ｔ）の２乗－ａ ＝ｘ１の２乗＋２（ｘ１）（ｐのｋ乗）ｔ＋（（ｐのｋ乗）の２乗）（ｔの２乗）－ａ ＝（ｘ１の２乗－ａ）＋２（ｘ１）（ｐのｋ乗）ｔ＋（（ｐのｋ乗）の２乗）（ｔの２乗） ＝（ｐのｋ乗）ｓ＋２（ｘ１）（ｐのｋ乗）ｔ＋（（ｐのｋ乗）の２乗）（ｔの２乗） ＝（ｐのｋ乗）（ｓ＋２（ｘ１）ｔ＋（ｐのｋ乗）（ｔの２乗）） ここまではいいのですが ｓ＋２（ｘ１）ｔ≡０（ｍｏｄ ｐ）となるようにｔを選ぶことができるというのがわかりません。 ここを通過すればｐのｋ＋１乗を約数にもつことになって証明が終わります。
- ベストアンサー
- 数学・算数
- 大学数学（関数 ラグランジュ補間多項式）の問題です
次のような問題の考え方、解法をを教えてください。 補間点をX0 = -2, X1= -1,X2= 1とし、これらの補間点での関数値をf0=9, f1= -2,f2= -12とする。 ラグランジュ補間多項式をP(X)=A(X-X1)(X-X2)+B(X-X0)(X-X2)+C(X-X0)(X-X1)と表したとき、A、B、Cに入る値を求めよ。 （X0 , X1,X2,f0, f1,f2の数字は下付） 答 A＝３、B＝１、C＝－２
- 締切済み
- 数学・算数
- 【Ruby】n=2;eval$s=%q{Z=?\s
【Ruby】n=2;eval$s=%q{Z=?\s;eval"$><<S=Z*4"+(%w{+"n=#{-~n%3};eval$s=%q{#$s}#YE";$>.isat ty&& (r="\e[43;3#{C="#{n*5%9+1}m"}#{T}\e[4"+C+S[1568,79]+E="\e[0m";r[81,21]="\e[37m# {(["Ca f\u00e9_au_lait","Yogurt","Fruit_mix"][n].chars*Z).tr(?_,"").center(21)}\e[3"+C ;a=%~POS A[`ER]`PASX1cTc22V6NNP.QOYGMXXIG7KK:bCCaVN8WZ[]UQMMS`cBFFJJHHY`QTUIUURRPTOcRV_a LLUT`WXL W]a_c_bV`XXYa_9}+[T=' B A L A N C E D F O O D ']*0+%w{bZZYb_][9cc ????`9^acG G,,N9DU`DKcUKU3K4!4!4!QXTSSS""9`9`#U`KcK--S;;/GOT<QE$U=>F==Q0@%U/P/B=S0Q`PM&XVV V15CMRHMSH RKO>==QMQVR 'b`&DK>BS<XE$T>T33DDDUM<V@@E(((TCT0A<0A"')5CXPcQa54X@@Y#KcK--S;; /GOT<Q`$)T)T :a4A%%#X VS6a ' b`&DK>BS<T7**] ^^b6+++]~; P=Str uct.new(:x,:d,:p,:v );M=(-5**7.. b=0).m ap{[]};A=s =[];t=Time.now;q=?y.succ;( s=S .scan(/.+/ );M[0]<<P [25i-b%3*5i- 9,0,0 ,2+1 i] ;6 0.t ime s { |i |j= i %2 0 ;i< 40 ? [ M[j -1],m=M[j],M [j+1 ]]. ea ch {| n| m. ea ch {| p| n. ea ch {| q| d=p .x -q .x ;w=d.abs-4;w <0& &( i<2 0? p. d+= w *w: p. p+= w *( d *(3 -p. d- q.d) +(p.v-q.v)*4 )/p .d )} } } :M . shif t .ea c h{ |p| y, x= ( p. x+= p.v +=p.p/10).re ct; p.p = [4 3- b/9 .0-y,1 ]. m in- [x,p .d=0 , x -9 2].s ort[1]*2i;p. v/=[ 1,p.v.a bs/2].max;M[20-j+[0 ,(x+ 4).div(5 ),19].sort[1]]<<p;35.tim es{|w|v=x.to _i-3+w %7;c=s[w=y.div(2)-2+ w/7];(x-v)**2+(y-w*2)**2<16&&0<=w&&c &&(k=(w*2-21 )**2/99)<=v&&c[v]&&k+79!=v&&c[v]=q}}};(24-b/18..21).map{|k|s[k]=Z*(k=(k*2-21)** 2/99)+q*79 +Z+q*2*(6-k)};s*="\e[B\r";" Your favorite flavor ";b+=1;A<<"\e[A\r"*21+s.gsub (/\172+/){ "\e[43m"+$&.tr(q,Z)+E})while+s.count(q)<1950;A.map{|q|sleep([t-Time.now+3,2e-2] .max);$> <<s=q};$><<s.gsub(?m,";33m").gsub(Z){S.slice!(/./)};b=?]*33.upto(91){|i|a=~/../ ;a=$'.gs ub(i.chr,$&)}*2;Z<<8;(b+a.gsub(?^,"^]"*41)+b).bytes{|c|c-=86;c<8?sleep(3e-2):$> <<(c<( 'CalorieMate-Liquid-Quine';9)?r.slice!(/\e.*?m|./):c>9?"\e[%X"%c:Z)});puts})*"" }#YE 質問 これを実行すると結果は何と表示されますか？ オンラインエディタ上で実行しても何も結果がコンソール画面に表示されませんでした。 これはルビーコードではないのですか？どういう意味が含まれているソースコードですか？
- ベストアンサー
- Ruby
- ラグランジュの補間について
ラグランジュの補間の導出にて 多項式近似にて近似式をＰｎ（ｘ）とすると ｘとｆ（ｘ）が既知の場合 Ｐｎ（ｘ）＝Σｆ（ｘｋ）Ｑｋ（ｘ） （ｋ＝０，１，・・・・ｎ） のように仮定して未知関数Ｑｋ（ｘ）を求めますが、 イメージがわきません。 どうして、このように仮定するのでしょうか？
- ベストアンサー
- 数学・算数
- Henselの補題の証明で質問です。
Henselの補題の証明で質問です。 よろしくお願い致します。 [命題(Henselの補題)] pを素数とするとZ[x]∋f(x)はモニックでdegf(x)≧1とする。 もし,GCD{g(x),h(x)}=1なるモニックなg(x),h(x)∈Z[x] (但し,degg(x),degh(x)≧1, f(x)=g(x)h(x) (mod p) …【1】) が存在するなら g_1(x)=g(x),h_1(x)=h(x), g_k(x)≡g_{k-1}(x) (mod p^{k-1}) (但し,k>1) h_k(x)≡h_{k-1}(x) (mod p^{k-1}) (但し,k>1) f(x)≡g_k(x)h_k(x) (mod p^k) (但し,k≧1) …【2】 なるモニックの列{g_k},{h_k}⊂Z{x]が存在することを示せ。 という問題です。 [証] kについての帰納法で示す。 (i) k=1の時,仮定【1】よりg_1(x):=g(x),h_1(x):=h(x)と採ればf(x)=g_1(x)h_1(x)と書ける。 そこで (ii) k≧1の時,g_1,g_2,…,g_k,h_1,h_2,…,h_kが【2】を満たすと仮定すると…【3】 GCD{g_k(x),h_k(x)}=1なので、、、 と続く予定なのですが GCD{g_k(x),h_(x)}=1となる理由が分かりません。 『∵【3】(帰納法の仮定)より, g(x)≡g_1(x)≡g_2(x)≡…≡g_k(x)(mod p),h(x)≡h_1(x)≡h_2(x)≡…≡h_k(x)(mod p)となる。 この時,GCD{g(x),h(x)}=GCD{g_1(x),h_1(x)}=…=GCD{g_k(x),h_k(x)}=1』 が言えれば ∃α(x),β(x)∈Z[x];α(x)g_(x)+β(x)h_k(x)=1…【4】(∵某命題). そして今,f(x)≡g_k(x)h_k(x) (mod p^k) (∵【3】(帰納法の仮定))が成り立っているから, f(x)-g_k(x)h_k(x)=p^kF(x)…【5】. 従って f(x)=g_k(x)h_k(x)+p^kF(x)=g_k(x)h_k(x)+p^kF(x)・1=g_k(x)h_k(x)+p^kF(x)(g_k(x)α(x)+h_k(x)β(x)) =g_k(x)h_k(x)+g_k(x)p^kα(x)F(x)+p^kβ(x)F(x)h_k(x) =g_k(x)h_k(x)+g_k(x)p^kα(x)F(x)+p^kβ(x)F(x)h_k(x)+p^{2k}α(x)β(x)F(x)^2-p^kα(x)β(x)F(x)^2 =(g_k(x)+p^kβ(x)F(x))(h_k(x)+p^kα(x)F(x))-p^{2k}α(x)β(x)F(x)^2で g_{k+1}:=(x)g_k(x)+p^kβ(x)F(x)、h_{k+1}:=h_k(x)+p^kα(x)F(x) …【6】と置けば g_{k+1}(x)≡g_k(x) (mod p^k) and h_{k+1}(x)≡h_k(x) (mod p^k) (∵【6】). 従ってf(x)-g_k+1(x)h_k+1(x)=f(x)-(g_k(x)+p_kβ(x)F(x))(h_k(x)+p^kα(x)F(x)) =(g_k(x)+p^kβ(x)F(x))(h_k(x)+p^kα(x)F(x))-p^{2k}α(x)β(x)F(x)^2-(g_k(x)+p^kβ(x)F(x))(h_k(x)+p^kα(x)F(x))=-p^{2k}α(x)β(x)F(x)^2 ≡0 (mod p^{k+1}) (∵≡の定義), つまり f(x)≡g_k(x)h_k(x) (mod p^{k+1}). 従って ∀k∈Nに対して, 【2】が成り立つ。 (終) という風に証明に至れるのですが『 』の箇所がどうして成り立つのかがいません。 どうすれば『 』は成り立ちますでしょうか?
- ベストアンサー
- 数学・算数
お礼
ありがとうございました。理解できました。