array(5) { ["chapterid"]=> string(8) "49409223" ["articleid"]=> string(7) "7300050" ["chaptername"]=> string(8) "第30章" ["content"]=> string(3358) "Crypto题他选了一道四星的椭圆曲线离散对数。椭圆曲线加密是比RSA更新的一类数学加密法——RSA用的是大数分解,椭圆曲线用的是一种叫"离散对数"的数学难题。简单说就是:在一条曲线上,你从起点出发,走k步到达终点,别人看到起点和终点,但算不出你走了几步。加密时你藏着"走了几步"这个数字当私钥,别人破解不了。
题目给了起点和终点,要求你算出走了几步。但曲线的"阶"——也就是这条路上一共有多少个落脚点——是一个合数,可以分解成几个小素数的乘积。
陈逸飞用了一个叫Pohlig-Hellman的算法。思路很巧妙:既然这条大路可以分解成好几条小路的组合,那就在每条小路上分别算"走了几步",最后把答案拼起来。就像一把大锁拆成了好几把小锁,每把小锁单独撬开,然后组合成大锁的答案。
但在小路上的计算,他用了BSGS算法——Baby-step Giant-step,翻译过来叫"小步大步"。原理是先走一小步一小步地把所有可能的位置存下来,然后大步大步地跳着去找匹配。优点是快,缺点是占内存——你要把小步的结果全存下来。
周可然看到他在做这道题时,停下了自己的操作,走到他身后看了一会儿。
"你的Pohlig-Hellman实现里,小素数阶的离散对数用的是BSGS。"周可然说。声音不大,但工位区安静,听得很清楚。
"对。"陈逸飞没回头。
"阶数最大的那个素因子是47bit。BSGS在这个大小上内存开销会很大——你要存大概两个G的数据。应该用Pollards rho。"
Pollards rho是另一种算法——不存数据,用随机走的方式找答案。慢一点,但几乎不占内存。就像找东西:BSGS是把整个房间扫一遍拍下来,Pollards rho是闭着眼在房间里乱转,转到碰上为止。
陈逸飞停下了敲键盘的手。转过头来看周可然。那个目光跟平时不一样——不是平时那种什么都收进眼底的平缓,而是收窄了,聚焦了。
"Pollards rho在47bit上期望迭代次数是多少?"他问。语气不像在质疑,更像在验证——一个工程师听到替代方案时第一反应是确认参数。
"大约2的23.5次方。跟BSGS的计算量差不多。但BSGS要把所有结果存下来——两个G以上。Pollards rho慢一些,可能是两到三倍时间,但内存几乎不占。"
"靶场内存限制——"
"512M。你BSGS跑不完。"
陈逸飞看了她三秒。
三秒不长,但在安静里显得很清楚。他的目光从周可然脸上移到她的B5笔记本上——翻开着,密密麻麻写着椭圆曲线公式和参数计算,字迹端正,每行公式后面都有注释。不是在抄书,是自个儿推导的。
然后他把屏幕上的BSGS代码全删了,从头写Pollards rho。十五分钟。没有抱怨,没有犹豫,没有"让我想想"的过渡。删,重写,跑,验证。
林墨在旁边看到了这一幕。
周可然对陈逸飞说的话,跟他对赵一鸣说的话,形式上完全不同——周可然没有指出陈逸飞的思维盲区,她指出的是一个纯技术的更优解。但本质一样:一个人在另一个人的操作中看到了可以改进的地方,然后说了出来。" ["create_time"]=> string(10) "1785963706" }