- ベストアンサー
Sku
- みんなの回答 （4）
- 専門家の回答
質問者が選んだベストアンサー
漫画では，「400年間，世界の謎とされたフェラーの定理」というように，デフォルメされているので，なんともいえないのですが， 1)φはオイラー関数という関数で，p,q,r,…が異なる素数なら φ(p)=p-1,φ(pq)=(p-1)(q-1),φ(pqr)=(p-1)(q-1)(r-1),… という値をとります(例：φ(15)=(3-1)(5-1)=8)。 M^{φ(n)}=1 (mod n)ですね。(例：1^8=2^8=4^8=7^8=8^8=11^8=13^8=14^8=1mod15) また，ウィルソンの定理は，(p-1)!=-1 mod p です（例：4!=24=-1mod5)。 2)Skuというのは，漫画に出てくる佐久シゲル教授の名前と推測されますが，実際は現在最も一般的な（すなわち安全と評価されるのですから最終暗号です）RSA暗号のようですね。それは， ア）受信者は大きな素数p,qを選び，ed=1 mod φ(pq) となるedを選びます。 イ）N=pqとeを公開します(p,q,dは非公開）。 ウ）送信者はXを送りたいときに，X^e mod N を送ります。 エ）受信者は受け取ったCに対し，自分しか知らないdを使って，C^d mod N を計算しXを取り出します。 C^d=(X^e)^d=X^{ed}=X^1=X mod N ここで，1)の２番目の公式を使いました。 一般に，これはdを知らないと元に戻せない， ← φ(N)が分からないとdが分からない ← Nが素因数分解できないとφ(N)が分からない ということからp,qを大きければ安全（受信者だけにXが伝わる）という訳です。 したがって,漫画は間違っていて， Sku^{-1} e,N(C)=C^d mod N が正しい。 うーむ，高校レベルかなぁ・・・？？？ 詳しくはRSAで検索してみましょう。
その他の回答 (3)
どうも。読んでみました。 けど、新しい小ネタは披露できそうにないので 佐久教授の話をします。 おそらく佐久教授のモデルはポールエルディシュです。 webで探してもいいページがないですが、 かなりの奇人だそうで、どこにいるかが いつも把握できなかったそうです。 で、自分の金を問題の懸賞金にしていました。 おしくも数年前に亡くなりました。 ただし、紫暗号とエルディシュは(おそらく)関係ないです。 紫暗号開発もそれなりの数学の素養が必要なので 当時の日本では有名な数学者だったはずなんですけど、 これもweb上には情報がないです。
マンガ/ドラマ/小説にでてくる数学/物理の知識にツッコミをいれるのが趣味です。 何巻に出てますか?検討してみます。 このへんの式は暗号に使われているので そういう話のときに出てきたんだと思いますが。 表現は間違っていますが、 m^(p-1)modP=1 フェルマーの小定理 Ｍφ(n)＝１(mod n) オイラーの定理 (P!)p=(p-1)=-1（modP） ウイルソンの定理 と呼ばれているものに相当するんじゃないでしょうか。
1)についてのみ 実在はすると思います。 中国の剰余定理というので調べればあるかもしれません。 ただ私も習って間もないので意味までは…。 とりあえずmodの使い方だけでも… 整数a,bとmについて、aとbがmで割ったときのあまりが等しいとき a≡b mod m と書きます。 φは多分写像の事なのではないでしょうか？ 私はこれを大学の講義で習いました。 高校生レベル… 頑張って勉強して下さい(^_^;)
関連するQ&A
- RSA暗号の中国剰余定理についておしえてください.
RSA暗号の中国剰余定理についておしえてください． N=77 = 7×11, p1=7, p2=11 d1 = d mod (p1-1) = 43 mod (7-1) = 1 d2 = d mod (p2-1) = 43 mod (11-1) = 3 m1 = c^d1 mod p1 = 48^1 mod 7 = 6 m2 = c^d2 mod p2 = 48^3 mod 11 = 4^3 mod 11 = 9 連立方程式 m = 6 mod 7 m = 9 mod 11 となり p1=7とp2=11は共に素数であるので互いに素 q1=p2^-1 mod p1 = 11^-1mod 7=4^-1mod 7=2 /// q2=p1-^1 mod p2 = 7^-1mod 11=8 //// これを用いて m=(m1×p2×q1 + m2×p1×q2) mod p1p2 = (6×11×2 + 9×7×8) mod 77 = (132+504) mod 77 = 20 平文 m = 20 とあるのですが，q1=p2^-1 mod p1 = 11^-1mod 7=4^-1mod 7=2と q2=p1^-1 mod p2 = 7^-1mod 11=8の部分でどうして2と8になるのかがわかりません．1時間くらい悩んでいるのですが見当がつきません．教えて下さい．＞＜
- 締切済み
- その他([技術者向] コンピューター)
- 変数の受け渡し double
関数の中にある変数の型を変えたら不具合が出たのでそのことに ついて質問します。 ある変数値が負である関数のdouble型変数に受け渡した後に値が変わりました。 本でdoubleの範囲を調べると1.7 * 10^(-308) ～ 1.7 * 10^(+308) と書いてありました。doubleに負の数値を代入してはまずいのでしょうか？ 具体的なプログラムを下に載せます。 int mod(double x,int p) { int ans; printf("x=%f prime=%d ",x,p); if(x >= 0){ if(x >= p) { ans=fmod(x,p); printf("fmod=%d\n",ans); }else{ ans=x; printf("mod=%d\n",ans); } }else{ do{ x+=p; }while(x < 0); ans=x; printf("mod=%d\n",ans); } return ans; } int rmd(struct zahyo *P,struct zahyo *Q,int prime) { unsigned int m,n; m=mod(Q->x - P->x,prime); n=mod(Q->y - P->y,prime); exeuclid(m,prime,1,0,0,1); printf("m=%d n=%d aa=%d aa*n=%d\n",m,n,aa,aa*n); return mod(aa*n,prime); } 実行結果の一部 m=10 n=6 aa=-1 aa*n=-6 x=4294967290.00000 prime=11 fmod=9 関数modのdouble型変数に負の数を受け渡すのはここ以外にもありますが このときだけ他の数値になりました。 考えられる原因は何かあるでしょうか？よろしくお願いします。
- ベストアンサー
- C・C++・C#
- 合同式の証明について
自分の使っている参考書に書かれている合同式の証明で a≡c (mod m) b≡d (mod m)より a-c=mp b-d=mq (p,qは整数)とおくことが出来る。 よって (a+b)-(c+d)=(a-c)+(b-d)=mp+mq=m(p+q) (a-b)-(c-d)=(a-c)-(b-d)=mp-mq=m(p-q) ab-cd=(c+mp)(d+mq)-cd=m(cq+pd+mpq) ゆえに(a+b)-(c+d),(a-b)-(c-d),ab-cdはmの倍数であるから a+b≡c+d(mod m) a-b≡c-d(mod m) ab≡cd(mod m) は成り立つ。 と書かれているのですが、全体的によく理解が出来ません。 まず なぜ a≡c (mod m) b≡d (mod m) であれば a-c=mp b-d=mq (p,qは整数)と、おくことが出来るのかということと ab-cdからどのような計算をすると(c+mp)(d+mq)-cd このようになるのかもわかりません。 数学はあまり得意ではないので中学生レベルの学力でも理解できるように 説明していただけると有り難いです。
- ベストアンサー
- 数学・算数
- 微分方程式
cosh(x) の定義は(e^x+e^{-x})/2 sinh(x) の定義は(e^x-e^{-x})/2です。 なので、A_1, A_2 を任意定数として A_1 e^x + A_2 e^-x とあらわせる式は、 A'_1, A'_2 を適当に置きなおすと、A'_1 cosh(x) + A'_2 sinh(x) と置きなおすことができるのですが、次の問題が分かりません。 {(d/dx)^4}u=Pu, (0<x<1), u(0)=u'(0)=0, u(1)=u'(1)=0 の問題についてですが D=d/dxとして特性方程式を作って {D+i[4]√(P)}{D-i[4]√(P)}{D+[4]√(P)}{D-[4]√(P)}=0 (ここで 累乗根 : x[n]√(a+b) = (x)(a+b)^(1/n) とする) とすると根がx = ±[4]√(P),±i[4]√(P)となり、一般解は公式より u=c1e^(-ix[4]√(P)) + c2e^(ix[4]√(P)) + c3e^(-x[4]√(P)) + c4e^(x[4]√(P)) (c1,c2,c3,c4は任意定数) となる。ココから次の式に導くのですがそれが分かりません。 u=c'1cosh(x[4]√(P)) + c'2sinh(x[4]√(P)) + c'3cos(x[4]√(P)) + c'4sin(x[4]√(P)) (c'1,c'2,c'3,c'4は任意定数) いろいろ試してみたのですが、出来ませんでした。 分かる方教えてください。お願いします。
- 締切済み
- 数学・算数
- 中国の余剰定理の応用
find all the solutions of each of the following congruences. a) x^3+8*x^2-x-1≡0(mod 11) b) x^3+8*x^2-x-1≡0(mod 121) c) x^3+8*x^2-x-1≡0(mod 1331) d) x^3+8*x^2-x-1≡0(mod 77) e) x^3+8*x^2-x-1≡0(mod 847) これはどうやって解けばいいのでしょうか？ modが11, 11^2, 11^3, 7*11, 7*11^2と11の倍数なのでそれを使う事はうっすらとわかるのですがいかんせん、わかりません。 a)はx≡4(mod 11), x≡5(mod 11)までは出せました。 これを連立合同方程式で解いて(a)は完了でしょうか？ b、c、d、eもはどうすればいいのでしょうか？
- ベストアンサー
- 数学・算数
- 高校数学の確率の問題です
右図のように12個の点A,B,C,D,E,F,G,H,K,Lが12本の線で結ばれている 粒子Pが点Aを出発してこれらの12個の点の間を次の規則に従って移動する (i)粒子Pは点ABCDの各点では上下左右のいずれか隣の点へ同じ確率1/4で1秒間で移動する (ii)粒子Pが×印の付いた点GKのいずれかに達すれば直ちに消滅する (iii)粒子Pが○印の付いた点EFHIJLのいずれかの点に達すれば以後その点で停止し続ける 出発してからn秒後に粒子Pが消滅する確率をp[n],停止する確率をq[n]とする、このとき、 (1)粒子Pが消滅する確率Σ[n1→∞]p[n],および停止する確率Σ[n1→∞]q[n]を求めよ (2)粒子Pが消滅するか停止するまでの時間の期待値Σ[n1→∞]n(p[n]+q[n])を求めよ 解説で粒子Pが0,2,4,,,秒後にA,Cにある確率の総和をそれぞれP(S),P(C)とし、1,3,5,,,秒後にB,Dにある確率の総和をそれぞれP(B),P(D)とする 対称性からP(B)=P(D)=xとすると P(A)=1+2x/4,P(C)=2x/4 粒子Pが移動し続ける事象Mの確率はp(M)=1×2/4×1/4×1/4×・・・・＝0となっていたのですが、 P(A)=1+2x/4,P(C)=2x/4になるのとp(M)=1×2/4×1/4×1/4×・・・・＝0になるのが分かりません p(M)の式は最初の1は0秒後に必ずAにいるので1、1秒後はAからB,Dのいずれかに行く確率なので2/4ここまでは分かるのですが、2秒後BまたはDからそれぞれAかCに行く確率が1/4になっているのが分からないです、B,Dから次に繋がる場合の数はB,DからそれぞれAかCに行く場合の合計4通りでB,Dからの進み方はB→G,B→F,B→A,B→C,D→A,D→C,D→K,D→Jの全部で8通りです、この中で次につながるのが4通りですから 1秒後から2秒後に繋がる確率は4/8=1/2と思ったのですが、1/4になってて合わないですよね、この考え方はどこが間違っているのでしょうか？
- ベストアンサー
- 数学・算数
- a≡b(mod m),c≡d(mod m)⇒ac≡bd(mod m)の逆は成立つ?
こんにちは。 参考書に合同式3x+5≡7(mod11)の解き方が載ってまして 3x≡2(mod11) 12x≡8(mod11) x≡8(mod11) とすんなり解かれていたのですが 最後の部分は命題 a≡b(mod m),c≡d(mod m)⇒ac≡bd(mod m) (12≡1(mod11),x≡8(mod11)⇒12・x≡1・8(mod11)) の逆を使ったのかと推測しましたが一般に逆は成立つのですか? それとも別の命題を使われてるのでしょうか?
- ベストアンサー
- 数学・算数
- 二次合同方程式の解法過程について
Mr_Holland さんが以前回答された過程で、 「x≡±1 (mod 3)・・・・（１） ∴x=3n±1」・・・・・・（２） と 「±2n≡2 (mod 3)・・・・（３） この合同式は ±n=1 のとき成立するので・・・（４） ±n=3m+1 （m:整数）とおける。」・・・・・（５） の２つの展開が異なっているのが、よくわかりませんのでご教授願います。 【補足】 前者は展開が納得できるのですが、 後者は、 ±n=1(mod 3)から ⇔n=±1(mod 3)と同じだから、 ⇔n=3m±1と展開できるので、 （5）式±n=3m+1と異なります。 後者の妥当性が知りたいです。 以下、Mr_Holland さんからの 回答 2010-11-17 10:57:57 回答No.2 Mr_Holland ANo.1は煩雑でした。 もう少しスマートに計算することができましたので、以下に示します。 x^2≡7 (mod 27) ⇒x^2≡7 (mod 9) ⇒x^2≡1 (mod 3) ⇔x≡±1 (mod 3) ∴x=3n±1 (n:整数）とおける。 以下、複号同順とします。 x^2=(3n±1)^2= 9n^2±6n+1 だから x^2≡±6n+1≡7 (mod 9) ∴±6n≡6 (mod 9) ∴±2n≡2 (mod 3) この合同式は ±n=1 のとき成立するので ±n=3m+1 （m:整数）とおける。 x^2=9(3m+1)^2+6(3m+1)+1 =81m^2+72m+16 だから x^2≡18m+16≡7 (mod 27) ∴18m+9≡0 (mod 27) ∴2m+1≡0 (mod 3) この合同式は m=1 のとき成立するので m=3k+1 （k:整数）とおける。 x=3n±1=±(±3n+1)=±{3(3m+1)+1}=±(9m+4)=±{9(3k+1)+4}=±(27k+13) ∴x≡±13 (mod 27) ∴x≡13,14 (mod 27)
- 締切済み
- 数学・算数
- RSAのdはどう求める？
素数p = 3、q = 5 公開鍵N = pq = 15 公開鍵e=7 とした場合 d = 1/e mod(p-1)(q-1) となるそうですが、このdはどうやって求めるのでしょうか。
- 締切済み
- 情報工学
補足
１２９巻です。おっしゃるとおり暗号に使われています。作中では２）を使うと解読不可能な暗号が誰でも作れるとなっています。