Daisuke Ishii
Mar 15, 2018 · 11 min read

暗号の基盤にもなる抽象代数学の基礎をまとめました

イラン人家庭教師に数学教えてもらいました

今日スタートでオンラインで数学を教えてもらいました。
相手はイラン人暗号学修士のArman 。
BlockChainの研究をしています。
群論の中でもアーベル群などを教えてもらいました。

一番の学び;

下記の写真は “neipia to the power of 2k pi divided by n multiply i. k in Z.”と発音する事。普段使わないので難しいですよね。

逆に数学英語をマスターすれば、論理的記述の英語の方が数学の学習が進むかもしれません。実験的にしばらく抽象代数学頑張ってみます。

今日の教材:
http://www.math.mtu.edu/~kreher/ABOUTME/syllabus/GTN.pdf
http://www.jmilne.org/math/CourseNotes/GT.pdf

その他の学び;

RSA暗号における素因数分解の仕組み
NP問題
アーベル群(可換群)と非可換群
秘密をシェアする方法 Secret Sharing
暗号学 = 10% 統計学 + 90% 群論
ハッシュ関数 SHA256が安全な理由
BlockChainはElliptic Curve(楕円曲線暗号)
量子コンピュータ耐性のあるLattice Crypto(格子暗号)
ルービックキューブは群論的特性を持っている(位置や組合せにおいて)
トランプのシャッフルは群論的特性を持っている

群論は楽しいので皆でやりましょう:
http://eman-physics.net/math/lie01.html


群論とは

群論(ぐんろん、英語: group theory)とは、を研究する学問。 群の概念は抽象代数学における中心的な概念。

ベクトル空間などは、演算公理が付与された群と看做すことができる。

群論の方法は代数学の大部分に強い影響を与えている。

線形代数群リー群の理論は群論の一分野。 特に発展を遂げており、独自の適用範囲を持っている。

結晶や、水素原子などの構造の多くは、対称性の群(symmetry group)で表現できる。このように、群論は、物理学化学の中に多くの実例・応用例がある。

1960年代~80年代に発表された総計1万ページを超える論文によって、完全な有限単純群の分類が達成された。これは多くの数学者の共同作業の賜物であり、20世紀の数学の最も重要な業績の一つ。

(Wikipediaより)

可換群

数学、とくに抽象代数学におけるアーベル群(アーベルぐん、: abelian group[注釈 1])または可換群(かかんぐん、: commutative group)は、群演算可換、すなわちどの二つの元の積も掛ける順番に依らず定まる群を言う。名称は、ノルウェーの数学者ニールス・アーベルに因む[2][注釈 2]

アーベル群は環上の加群ベクトル空間といった抽象代数学の概念において、その基礎となる加法に関する群(加法群)としてしばしば生じる。任意の抽象アーベル群についても、しばしば加法的な記法(例えば群演算は “+” を用いて表され、逆元は負符号を元の前に付けることで表す)が用いられ、その場合に用語の濫用で「加法群」と呼ばれることがある。また任意のアーベル群は整数全体の成す環 Z 上の加群とみることができ、その意味でやはり用語の濫用だがアーベル群のことを「加群」と呼ぶこともある。

一般に可換群は非可換群英語版)に比べて著しく容易であり、とくに有限アーベル群の構造は具さに知られているが、それでも無限アーベル群論はいまなお活発な研究領域である。

(Wikipediaより)

NP問題

NP困難(エヌピーこんなん、: NP-hard)とは計算量理論において、問題が「NPに属する任意の問題と比べて、少なくとも同等以上に難しい」ことである[1]。正確にいうと問題 H がNP困難であるとは、「NPに属する任意の問題 LH へ帰着可能である」と定義される。この「帰着」の定義として何を用いるかにより微妙に定義が異なることになるが、例えば多項式時間多対一帰着多項式時間チューリング帰着を用いる。NP困難問題を解ける多項式時間の機械がもしあれば、それを利用してNPに属するどの問題も多項式時間で解くことができる。

NP完全問題とは、NP困難であり、かつNPに属する問題である。これと異なり、NP困難である問題はNPに属するとは限らない。NP決定問題のクラスなのでNP完全もまた決定問題に限られるが、定義に用いる帰着の種類によってはNP困難には決定問題、探索問題(en)、組合せ最適化問題など様々な問題が属しうる。

上に挙げた定義から、問題 H がNP困難なとき次のことが言える(以下は定義ではなく主張)。

  • すべてのNP完全問題は H に還元して多項式時間で解ける。またNPに属する全ての問題も H に還元できる。
  • もし最適化問題 H の特殊例としてNP完全な決定問題 L を考えられるなら、H はNP困難である。

NP困難な組合せ最適化問題は、一般に最適解を求めるのが非常に困難であると考えられているため、近似アルゴリズムに関しても研究されている。

(Wikipediaより)

楕円曲線

(BlockChainの基盤になっている楕円曲線暗号に通じます)

数学における楕円曲線(だえんきょくせん、: elliptic curve)とは種数 1 の非特異射影代数曲線、さらに一般的には、特定の基点 O を持つ種数 1 の代数曲線を言う[1]

楕円曲線上の点に対し、積に関して、先述の点 O を単位元とする(必ず可換な)をなすように、積を代数的に定義することができる。すなわち楕円曲線はアーベル多様体である。

楕円曲線は、代数幾何学的には、射影平面 P2 の中の三次の平面代数曲線として見ることもできる[2]。より正確には、射影平面上、楕円曲線はヴァイエルシュトラス方程式あるいはヴァイエルシュトラスの標準形

により定義された非特異な平面代数曲線に双有理同値である(有理変換によってそのような曲線に変換される)。そしてこの形にあらわされているとき、O は実は射影平面の「無限遠点」である。

(Wikipediaより)

電子割符

(暗号の実装には欠かせないコンセプト=Secret Sharing)

電子割符(でんしわっぷ)とは、秘密分散法を応用した暗号技術の一種、およびそれにより生成される分割された情報のことである。用いられた秘密分散法の特徴がそのままその電子割符の特徴[注釈 1]となる。1979年にShamirとBlakleyによってそれぞれ独立に異なる秘密分散法が提案されて以来、多くの秘密分散法が提案され、その数だけの種類の電子割符がある。

新たな情報運用管理手法を産み出す基礎技術として[1]、また機密情報保護の観点[2][3]から注目を集めている。

現実の割符と同様に一つの元の情報を二つ以上に分割し、またそれらを集めることで元の情報を復元する。現実の割符では主に、元の情報自体は既知で集めた時に既知の情報が得られたことを確認する相互認証[注釈 2]に用いられる[注釈 3]が、電子割符では、複数人の協力によってのみ得られる秘密情報の隠蔽[注釈 4]に用いられる。また現実の割符では不可能な、十に分けた電子割符の内のどれでも三つ以上が集まれば秘密情報を得られる等の閾値(この例では三つ)を指定する[注釈 5]などの高い可用性を持つ。

暗号技術の一種ではあるが、一般の暗号(秘匿通信)とは異なった利用法を前提としていることから暗号として単純に評価することができず、用いられた秘密分散法を評価しなければならない。表面的には「暗号文と暗号鍵に分ける」と認識しても大きな間違いではない(→#バーナム暗号との関係)が、それでは多くの電子割符が具備する高い可用性も広い応用範囲も説明できないことは留意しておくべきである。

(Wikipediaより)

リー群

G台集合とする実リー群とは、G には実数体上有限次元で(多くの場合無限回微分可能という意味で)可微分な実多様体の構造が定められていて、G はまた群の構造を持ち、さらにその群の演算である乗法および逆元を取る操作が多様体としての G 上の写像として可微分であるもののことである(群演算が可微分写像となっていることを「群演算が可微分多様体の構造と両立する(可換である、あるいはうまくいっている)」といい表す)。このような構造が入っているという前提の下で、通常は「G はリー群である」というように台を表す記号を使ってリー群を表す。また、実数(実多様体)を複素数(複素多様体)にとりかえて複素リー群の概念が定まる。

リー群の定義を圏論の言葉で述べれば、リー群とは可微分多様体の群対象のことであるということができる。

複素数C 上の二次特殊線型群 SL(2, C) などは複素リー群の例である。また、直交群や斜交群は、成分の属する体の直積位相からの相対位相に関して多様体とみるとリー群である。このような行列からなるリー群は総じて(代数的)行列群あるいは線型代数群と呼ばれる一類(正確には、ある代数閉体上の一般線型群の部分群であって、成分代数方程式によって与えられるもの)に属す。

一般化として、台となる多様体が無限次元であることを許すことにより無限次元リー群が同様の方法で定義される。また、類似物として係数の属する体を p-進数体にとりかえて p-進リー群が定義される。あるいは係数体を有限体に取り替えれば、リー群の有限な類似物としてリー型の群が豊富に得られるが、これらは有限単純群の多くの部分を占めるものである。また、可微分多様体を用いる代わりに解析多様体や位相多様体を台にすることもできるが、それによって新たなものが得られるというわけではない。事実、アンドリュー・グリーソンディーン・モントゴメリレオ・ジッピンらは1950年代に次のことを証明している。すなわち、G が位相多様体であって、連続な群演算をもつ群でもあるならば、G 上の解析的構造が唯一つ存在して、G をリー群にすることができる(ヒルベルトの第5問題あるいはヒルベルト-スミス予想)。

(Wikipediaより)

群論のブログ

Team AI Research

Research on Latest Machine Learning Technology. http://www.team-ai.com/ 機械学習の最新技術情報を分析しています

Daisuke Ishii

Written by

Founder of Jenio Inc & Machine Learning Community “Team AI” in Tokyo. http://www.team-ai.com/

Team AI Research

Research on Latest Machine Learning Technology. http://www.team-ai.com/ 機械学習の最新技術情報を分析しています

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade