命題 nを素数、aを1≦a≦n-1の自然数とするとき、 ある自然数b(1≦b≦n-1)が存在して、 ab≡1(mod n) となる。このようなbは1≦b≦n-1に唯1つである。 (証明は省略します) 上のような条件を満たす(a,b)をペアと考えます。 a=1,n-1のペアは自分自身で、2≦a≦n-2なるaのペアは自分自身でない、という事も証明できます。 (n-1)!=1*{2*・・・*(n-2)}*(n-1) の{}内に着目すると、 上の意味での"ペア"を{}の中で作る事ができます。 ペアの相方がいない、とか、ペアの相方が2つ以上ある、という事がありませんので、 例えば、n=7や11の場合に、{}内を並び替えると 6!=1*{(2*4)*(3*5)}*6≡1*{1*1}*6≡-1 (mod 7) 10!=1*{(2*6)*(3*4)*(5*9)*(7*8)}*10≡1*{1*1*1*1}*
☆HOME☆ ☆数学のいずみ☆ 高校生のための暗号論入門 @Author MASASI.Sanae @Version 1.04;2003.1.22 0.はじめに インターネットの普及に伴って,ネット上における情報の機密保持,改ざん防止の方法として公開鍵暗号方式が注目を集めている。公開鍵方式の中でも最も普及しているのがRSA暗号と呼ばれるものである。 この理論には基本的でかつ魅力的な数学の整数に関する理論が用いられている。高校数学レベルでも理解できる数学をもとに,暗号論の魅力を少しでも知っていただきたいと思う。 1.素数 1_1 素数・合成数 整数a(a≠1)が1とa以外に約数をもたないときaを素数という。また素数でない整数を合成数という。(素数一覧参照) (例)7,11は素数。 12=22・3は合成数。 1_2 素数判定アルゴリズム 素数を完全に定義する式が存在することは証明されていない
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く