[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,单向函数的强度取决于反向过程所需要的时间
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,即便是借助地球上最强大的计算机
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,要遍历所有可能情况也需要上千年时间
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,那么想解密是不切实际的
Dialogue: 0,0:00:01.65,0:00:05.72,Default,,0000,0000,0000,,我们需要一种朝一方向易朝反方向难的数值过程
Dialogue: 0,0:00:05.72,0:00:07.79,Default,,0000,0000,0000,,我们需要一种朝一方向易朝反方向难的数值过程
Dialogue: 0,0:00:07.79,0:00:12.69,Default,,0000,0000,0000,,于是我们找到了模算术 它也叫作时钟算术
Dialogue: 0,0:00:12.69,0:00:20.12,Default,,0000,0000,0000,,比如 要求46除以12的余数
Dialogue: 0,0:00:20.12,0:00:24.51,Default,,0000,0000,0000,,我们可以取一根长46单位的绳子
Dialogue: 0,0:00:24.51,0:00:28.32,Default,,0000,0000,0000,,将其缠绕在12单位的时钟周围 12也就是模数
Dialogue: 0,0:00:28.32,0:00:32.88,Default,,0000,0000,0000,,绳子终止的地方也就是答案
Dialogue: 0,0:00:32.88,0:00:39.44,Default,,0000,0000,0000,,因此记作46 mod 12 ≡ 10
Dialogue: 0,0:00:39.44,0:00:44.19,Default,,0000,0000,0000,,很简单
Dialogue: 0,0:00:44.19,0:00:48.51,Default,,0000,0000,0000,,下面 我们考虑用质数做模数 比如17
Dialogue: 0,0:00:48.51,0:00:52.74,Default,,0000,0000,0000,,我们找到17的一个原根 这里也就是3
Dialogue: 0,0:00:52.74,0:01:00.10,Default,,0000,0000,0000,,它具有如下重要性质 取不同幂次时
Dialogue: 0,0:01:00.10,0:01:05.51,Default,,0000,0000,0000,,结果会在时钟上均匀分布
Dialogue: 0,0:01:05.51,0:01:08.86,Default,,0000,0000,0000,,3是一个生成元
Dialogue: 0,0:01:08.86,0:01:14.04,Default,,0000,0000,0000,,取3的x次方
Dialogue: 0,0:01:14.04,0:01:17.74,Default,,0000,0000,0000,,结果等可能地出现在0和17中间任何整数上
Dialogue: 0,0:01:17.74,0:01:20.42,Default,,0000,0000,0000,,但相反的过程就难了
Dialogue: 0,0:01:20.42,0:01:23.69,Default,,0000,0000,0000,,比如 给定12 要求这是3的多少次方
Dialogue: 0,0:01:23.69,0:01:30.22,Default,,0000,0000,0000,,这被称为离散对数问题
Dialogue: 0,0:01:30.22,0:01:32.61,Default,,0000,0000,0000,,这样我们就有了单向函数
Dialogue: 0,0:01:32.61,0:01:39.07,Default,,0000,0000,0000,,一个方向很容易 但反向就很难了
Dialogue: 0,0:01:39.07,0:01:42.09,Default,,0000,0000,0000,,已知12 我们只能采用试错法 求出匹配的指数
Dialogue: 0,0:01:42.09,0:01:47.32,Default,,0000,0000,0000,,这有多难呢
Dialogue: 0,0:01:47.32,0:01:49.75,Default,,0000,0000,0000,,如果数字很小 这还很容易
Dialogue: 0,0:01:49.75,0:01:53.75,Default,,0000,0000,0000,,但模数若是长达数百位的质数