アクセスカウンター

  • 1本記事閲覧者数   👀💡:
  • 22今日の足あと    🦶💮:
  • 2832サイト訪問者数(累計)🦶💡:

DataEntrepreneurFellows コンピュータサイエンス コンピュータ 学びのアウトプット

【学びのアウトプット】コンピュータサイエンス〜RSA公開鍵暗号方式〜

更新日:

 

どうも、solobochiです。

 

 

今年度受講している文部科学省のデータ関連人材育成の学習プログラムでコンピュータサイエンスについて学習しましたのでまとめておきます。

 

 

 

目次

  1. コンピュータサイエンス
  2. ユークリッド互除法
  3. フェルマーの小定理
  4. 因数分解の計算量
  5. RSA公開鍵暗号
  6. 量子コンピュータ

7/27更新 Update

 

 

コンピュータサイエンス

👉コンピュータの科学、では直訳ではあるが説明としては不十分。

👉Wikiによれば、情報と計算の理論的基礎、およびそのコンピュータへの実装・応用に関する研究分野

👉正確には、情報処理・問題処理をコンピュータの計算手順に転換することにより自動化する方法を発見する研究分野
→すなわち、言い換えれば、コンピュータシステムを作るための科学

👉具体的な研究分野としては、プログラミング言語論、計算理論・計算の基礎、アルゴリズム論、人工知能、自然言語、ソフトウェア工学、etc

 

 

ユークリッドの互除法

👉2つの自然数の最大公約数を求めるアルゴリズム

└アルゴリズムとは:問題を解く手順について定式的に表現したもの。計算可能なもの(=チューリングマシンで解くことができるもの)を計算するためのもの。

👉人類最古のアルゴリズム

🔸アルゴリズムは以下の通り

ユークリッド互除法

\displaystyle  a = b \times q+ r となるa,bについての最大公約数を求める

ⅰ) 以下の式のx , yにそれぞれa , bを代入する
\displaystyle x = y \times q + r

ⅱ) y ≠ 0まで以下1,2を繰り返す

1.  x = y \times q + r
(xをyで割った商をq、余りをrとする)◀️a = bq + r が成り立つ時、aとbの最大公約数は、bとrの最大公約数に等しいことを利用する

2. xにyを代入、yにrを代入する

ⅲ) y = 0となった時のxの値が最大公約数

👉数式で簡潔に書くと、

ユークリッド互除法を数式で簡潔に表現

\displaystyle a = b \times q + rの時、

gcd (a , b) = gcd (b , r) = d

※gcd :greatest common divisor(最大公約数)

 

 

 

フェルマーの小定理

👉RSA公開鍵暗号にも応用されている素数に関する定理

フェルマーの小定理

素数p、pと互いに素である整数aについて

\displaystyle a^{p-1} \equiv 1(\mod{p})

 

 

因数分解の計算量

👉多項式時間で解ける素因数分解アルゴリズムは見つかっていない

因数分解の計算量

・計算量とは
→計算量理論:計算の複雑さを数学的に表現する
→入力サイズの関数で表現する
└→オーダー記法:O

・オーダー記法の一覧

オーダー記法(O) 内容
O(1) : 定数時間 データ数(N)によらず同じステップ数で実行できるアルゴリズム。
例)ハッシュ探索、ハッシュテーブルによるデータ検索、配列要素へのアクセス
O(\displaystyle \log{n}):対数時間 処理ごとに処理対象を減らすことのできるアルゴリズム。
データ数(N)が増えてもそれほど計算時間はほとんど増えない。
例)2分探索
O(n) : 線形時間 データ数(N)の分だけ時間がかかるアルゴリズム。
例)forループ1回分、未ソート配列の探索
O(\displaystyle N \times \log{N}):準線形/線形対数時間 O(n)相当のループとO(\displaystyle \log{n})相当のループが合わさったアルゴリズム。
例)クイックソート(基準値との比較でソート)、マージソート、ヒープソートなどの高速ソートアルゴリズム
O(\displaystyle n^2) : 二乗時間 O(n)相当のループを二重にしたアルゴリズム。全ての組み合わせのペアを調べるようなアルゴリズム。
例)バブルソート、挿入ソートなどの単純なソートアルゴリズム、工夫しないソートアルゴリズム。
O(\displaystyle k^N) : 指数時間 全ての組み合わせについて調べるようなアルゴリズム。パターンを列挙する必要がある問題は指数時間となる。
例)ルービックキューブの総当たりによる解法、素因数分解の試し割りによる解法
O(n!) : 階乗時間 Nの階乗に比例する時間がかかるアルゴリズム。
例)巡回セールスマン問題

 

因数分解の計算量(続き)

・整数Nを素因数分解するもっとも素朴な方法である、試し割り
→1から順に割っていき、\displaystyle \sqrt{N}まで割る
\displaystyle \sqrt{N}総当たりなので指数時間アルゴリズム

・コンピュータ内部では0、1の2進数で整数・状態を表現しているので、1ビットで10進数の1、2を表現する。
(※余談→ノイマン型:0か1、量子:0と1の重ね合わせを表現)
同様に、2ビットで、1〜4、3ビットで1〜8、、、、pビットであれば、\displaystyle \Large 2^{p}まで表現できる

Nを表現するために必要なビット数計算

整数Nを表現するために必要なビット数は、\displaystyle \log_2{N}ビット(※)
\displaystyle 2^p > N のとき

\displaystyle \log_{10}{2^p} > \log_{10}{N}

⇒ \displaystyle p \times \log_{10}{2} > \log_{10}{N}

⇒ \displaystyle p > \frac{\log_{10}{N}}{\log_{10}{2}}

∴ \displaystyle p > \log_{2}{N}

整数Nを素因数分解するアルゴリズムの計算量

\displaystyle N = 2^{\log_{2}{N}}

⇒ \displaystyle \sqrt{N} = 2^{\log_{2}{\frac{N}{2}}}より、

整数Nを試し割りで\displaystyle \sqrt{N}まで全て試していく方法の計算量は、\log_{2}{\frac{N}{2}}の指数時間アルゴリズムとなる

 

 

RSA公開鍵暗号

👉RSA公開鍵暗号の安全性は素因数分解の難しさ、計算量の大きさに依存している

RSA公開鍵暗号方式

・RSA公開鍵暗号とは
→素数p,qの積n(\displaystyle n = p \times q)とある整数eを公開鍵として公開しておき、暗号文を公開鍵で暗号化
※平文に対して、e乗してmod nを求める
→暗号文を平文にする際には、秘密鍵dを使って、暗号文をd乗してmod nを求めて平文にする
→p、qがわかっていれば簡単だが、p、qが分からない場合は、公開されているnからp,qを探さなければならない。この時素因数分解の計算量が膨大であることがRSA公開鍵暗号方式の安全性を保っている。

 

 

dav

 

量子コンピュータ

👉RSA公開鍵暗号方式は電子署名やメール、SSLサーバ認証(https)を用いたECなど今やありとあらゆる場面で利用されているが、量子コンピュータにより素因数分解の計算量が低コスト化すればRSA公開鍵暗号をはじめとする様々なセキュリティが破られることになる

Shorのアルゴリズム

・Shorのアルゴリズム
→Shorのアルゴリズムを用いると、素因数分解を効率的に解くことができる
→2n個の量子ビットがあれば、2^nの因数分解を効率的に解くことができる

 

 

 

 

以上

 

 

 

 

 

⬇️他にもよく見られている記事⬇️

最も訪問者が多かった記事 10 件 (過去 7 日間)
  • この記事を書いた人
  • 最新記事
アバター

solobochi

気づけば社会人10年目のアラサー。 いつのまにかまわりが結婚→出産→マイホーム、と順調に”しあわせ家族計画”を進めていくのを横目に見ながら、ふと人生見つめ直し、、、結果、絶賛模索中の日々🐠🏃‍♂️----------------- 学んだことのアウトプットや、日々つらつら思うことを整理して残しておくような雑記ブログ(にするつもり、、、、)(as U like / as I like / write freely)-----------------ただし如何せん不器用で、1つ1つ丁寧に積み上げていかないと理解できないので学習は遅い😓-----------------2018年東大松尾研DeepLearning講座受講。 2019年度データアントレプレナーフェロープログラム参加中。

おすすめ記事

1

  はじめまして solobochi(そろボチ)です。   生まれも育ちも東京で、大学も会社も東京です。ずっと東京にいます。 社会人になってボチボチ約10年。 バリバリの文系ですが ...

2

  どうも、solobochiです。   2019年に入ってからというもの、休日は割とpython触ってます。といってもまだ簡単なサンプルコードをなぞるだけですが。   ...

-DataEntrepreneurFellows, コンピュータサイエンス, コンピュータ, 学びのアウトプット
-, , ,

Copyright© そろボチ , 2019 All Rights Reserved Powered by AFFINGER5.