FC2ブログ

公開鍵に関しての説明

暗号理論でめんどくさいプログラムを組んだりする。
今回やったのは、高速べき乗法というもの。
Mathematicaで書いた。
 
MyPowerGCD[n_, c_, t_] := Module[{a, b, i = 1, z = 2, k = n, l = t},
a = c; b = {};
While[a > 0,
b = Prepend[b, Mod[a, 2]];
a = Quotient[a, 2]; i++
];
While[z < i, If[b[[z]] == 0, k = Mod[k^2, l], k = Mod[k^2*n, l]];
z++]
; k
]

解説をすると、これはこれをしたいのだ。
y = m^e mod[N]
ただ、eがものすごく大きいと計算が面倒だから、計算回数を減らすという試みだ。(別の名をバイナリ法ともいうらしい)
このeを2進数表記する。
たとえば、11=(1 0 1 1)<=[8 4 2 1]という風にする。(右側はbit)
そして、次のWhile文から先が、面倒だ。
この11の場合0から順に評価する。最初の1(頭)は無視する。
0ならばy^2mod[N]をし、1ならばy^2*y(元のy)mod[N]をする。まあ、プログラムした人ならわかるだろう。

こうしてできたものを利用する暗号がRSA暗号だ。
これは、素因数分解の難しさによって成立している。
勉強するだけならまだしも、ここらへんは大変辛い。
数学嫌いにはならないでほしいことを切に願う。
スポンサーサイト



非公開コメント

プロフィール

水妖の音楽

Author:水妖の音楽
京都大好き大学生。
2009年 天文学会参加
2013年 サマーチャレンジ  
2015年 夏の学校
現在天文学を勉強中の大学院生
主にあわぎゃらくしーをやっていますが、銀河とつけばなんでも面白がります。
思想の根本は荘子であるため誰かしらに与することはしません。
身体論、哲学の類いの話も好きです。
趣味は読書とクラシックと絵画をみること山登り。
籘真千歳先生のファンです。
SFが特に好きです。森見登美彦さんも好きでサイン本を持つほど。ライトノベルは半分の月がのぼる空。ホラーなら玩具修理者。
クラシックはアリシア・デ・ラローチャやバーンスタイン、佐渡裕、カツァリス等が好み。
絵はマグリットやら、ルドン、川瀬巴水、ドミニク・アングル

最新記事
最新コメント
Twitter
ゆるりと呟きます。呟くまえに喋ってしまいますが… 気になった方はフォローしてくれるとありがたいですが、人次第でブロックするかもしれません。そのときはごめんなさい。
月別アーカイブ
カテゴリ
バナー
初音ミク-Project DIVA-F 2nd
閃の軌跡
要予約
最新トラックバック