Return to Video

Discrete Logarithm Problem

  • 0:02 - 0:06
    我们需要一种朝一方向易朝反方向难的数值过程
  • 0:06 - 0:08
    我们需要一种朝一方向易朝反方向难的数值过程
  • 0:08 - 0:13
    于是我们找到了模算术 它也叫作时钟算术
  • 0:13 - 0:20
    比如 要求46除以12的余数
  • 0:20 - 0:25
    我们可以取一根长46单位的绳子
  • 0:25 - 0:28
    将其缠绕在12单位的时钟周围 12也就是模数
  • 0:28 - 0:33
    绳子终止的地方也就是答案
  • 0:33 - 0:39
    因此记作46 mod 12 ≡ 10
  • 0:39 - 0:44
    很简单
  • 0:44 - 0:49
    下面 我们考虑用质数做模数 比如17
  • 0:49 - 0:53
    我们找到17的一个原根 这里也就是3
  • 0:53 - 1:00
    它具有如下重要性质 取不同幂次时
  • 1:00 - 1:06
    结果会在时钟上均匀分布
  • 1:06 - 1:09
    3是一个生成元
  • 1:09 - 1:14
    取3的x次方
  • 1:14 - 1:18
    结果等可能地出现在0和17中间任何整数上
  • 1:18 - 1:20
    但相反的过程就难了
  • 1:20 - 1:24
    比如 给定12 要求这是3的多少次方
  • 1:24 - 1:30
    这被称为离散对数问题
  • 1:30 - 1:33
    这样我们就有了单向函数
  • 1:33 - 1:39
    一个方向很容易 但反向就很难了
  • 1:39 - 1:42
    已知12 我们只能采用试错法 求出匹配的指数
  • 1:42 - 1:47
    这有多难呢
  • 1:47 - 1:50
    如果数字很小 这还很容易
  • 1:50 - 1:54
    但模数若是长达数百位的质数
  • Not Synced
    单向函数的强度取决于反向过程所需要的时间
  • Not Synced
    即便是借助地球上最强大的计算机
  • Not Synced
    要遍历所有可能情况也需要上千年时间
  • Not Synced
    那么想解密是不切实际的
Title:
Discrete Logarithm Problem
Description:

Discrete Logarithm Problem - modular arithmetic
more » « less
Video Language:
English
Duration:
01:56
amyyan added a translation

Chinese, Simplified subtitles

Revisions

Our website uses cookies for analysis purposes.