YouTube

Got a YouTube account?

Νέο: ενεργοποιείστε μεταφράσεις και λεζάντες που δημιουργήθηκαν από θεατές στο κανάλι σας στο YouTube!

Japanese υπότιτλους

← Discrete Logarithm Problem

Discrete Logarithm Problem - modular arithmetic

Πάρτε τον Κωδικό ενσωμάτωσης
24 Γλώσσες

Υπότιτλοι μεταφρασμένοι από Αγγλικά Showing Revision 7 created 07/28/2013 by linoal.13.

  1. 「ある方向では簡単で、逆方向では難しい」

  2. そんな計算手順を考えましょう。
  3. ここで登場するのが、「合同算術」です。これは、「時計演算」とも呼ばれています。
  4. たとえば、46を12で割った余りを求める場合、46単位の長さのヒモを用意します。
  5. そして、そのヒモを周の長さが12単位の「法」と呼ばれる時計に巻き付けます。
  6. そして、ロープの端が来たところが解になります。
  7. ここでは 46 を 12 で割った余り、つまり剰余は 10 になります。
  8. 簡単ですね。これを機能させるために、まず17などの素数の「法」を扱います。
  9. 17の「原始根」を設定します。今回は3で考えます。
  10. 3には重要な性質があります。さまざまな指数で累乗したときに、
  11. 解が時計の周囲に均等に分散されるのです。
  12. 3は「生成元」と呼ばれています。3を任意の指数 x で累乗した場合、
  13. 解は、等しい頻度で、偏りなく、0と17の間の任意の整数になります。
  14. しかし、逆向きの演算は困難です。
  15. たとえば、3を何乗して17で割った余りが12になるか簡単に分かるでしょうか。
  16. これは「離散対数」の問題と呼ばれます。
  17. ここまで、一方向の関数について考えました。
  18. これは簡単に実行できますが、逆方向は難しい関数です。
  19. 12という数字が与えられても、それを生み出した指数を見つけるには、大変な試行錯誤が必要です。
  20. どれぐらい大変でしょうか。
  21. 小さな数字なら簡単です。けれど、何百桁にもなる素数の「法」を使用した場合、
  22. 実際には解くことができなくなります。
  23. 地球上のすべてのコンピュータを使っても、全ての可能性のある数を見つけ出すには、
  24. 何千年もかかってしまうでしょう。
  25. つまり、一方向関数の強みは、逆方向に計算するのに膨大な時間がかかるという点なのです。