title: 对一次寻找大素数问题的思考 date: 2015-10-25 13:49:37 mathjax: true tags:

  • 流水账

背景

我每过段时间,就会兴趣大发,噼里啪啦加上一堆qq群,一般就是最近在做相关的工作,或者想了解学习相关的知识,到现在已经加了几十群了。qq群对于我来说,一是看大家伙的讨论一些专业技术问题,一是从共享里面下载一些书籍资料,当然一般一个群建立的比较久了,群里活跃成员达到一定的数目,一个群也会有适当的灌水,娱乐一下,好像有点一个小社会的那么点意思。昨天加一个计算机相关的群,它设置了一个问题:

小于899808659的最大质数是?

低头做事

第一感觉是简单,应该能很快做出来,但随后也感觉这个数稍微有点大,会不会没自己想想的这么简单,也想到了三种可能能解决这个问题的方案:试除法(复杂度约为n^1.5)、欧拉筛法 和 Miller–Rabin素性检测,前两种解决方案以前都写过对应的C代码,第三种也就是知道名字能做什么而已。决定试一把前两种解决方案,感觉以前写过怎也能做出来。前两种选哪一种呢?我也说不太清楚,带着复杂的的心情写完了第一个方案的程序

在写程序的时候发现 899808659 本身就是一个素数,可惜题目要的是比这个数略小的。程序运行了10多分钟发现程序还在跑。感觉糟了要是要找的这个数和这个数差的范围太大怎么办?。然后直接放弃了想着写欧拉筛法吧,屋漏偏逢连阴雨,欧拉筛法忘记怎么写了,当时理解的不是很深刻的判断终止循环地方果然又记不起来原因了。琢磨半天搞明白后,开始写代码,写的时候发现分配数组太多,分配不了,在ruby下数组的大小也就能分配5亿个,在C语言中也是大概这么多个int类型的数组。但这个算法能在线性时间内筛除区间内的所有素数,感觉很有意思、神奇、实用,自己也快忘记具体细节了,就决定花点时间复习一下,顺带用ruby写了一个版本。显然最终还是没能解决最终的问题。

怎么办呢?怎么办呢?怎么办呢?

检索了一下,看了几篇文章,发现大素数及其判定问题原来是个国际性的难题。大素数的一个重要应用在RSA加密中。虽然899808659这个素数虽然不小了,但还是挺小的,也有一些ACMer公布了一些判断2^63内数的素性测试的现成程序,但战胜失败的强烈欲望我感觉非得写个程序搞定不可,不然太没面子了。然后开始跳入了一个深坑。参考 大素数判断和素因子分解(miller-rabin,Pollard_rho算法) 这篇blog,一开始怎么也不找头脑,想放弃,但是感觉放弃可不行啊,遇到困难就放弃怎么能学到东西呢?硬着头皮往前上,发现有段代码不懂,不知怎么脑洞突然大开,直接搜索这段代码,进入Miller-Rabin素数测试学习笔记这篇blog发现原来不理解的代码其实是二次探测定理的使用。总结起来这个理解算法的难点就可以归结为 理解代码中溢出的解决,二次探测定理,费马小定理等这些技术和原理。现在就等二次探测定理 归位,开工检索,检索到Matrix67先前有篇blog 数论部分第一节:素数与素性测试 里面有这个关键词。Matrix67是第一个让我深刻体会到blog还能这么有意思,细细品读,醍醐灌顶,这篇文章果然有没有失望,深入浅出,又是一片好文。折腾到晚上程序写完了。程序连接

程序输出来好多结果,感觉数字8一直没变,坏了,数据太多了。把2改大后结果一下就出来了

899808619

验证不过去,额,眼前一黑,Miller–Rabin那么低的概率判断失误的情况居然碰上了。

反正离899808659挺近的,就枚举一下(899808619,899808659)区间的数吧,实在折腾的够呛了,最后真正的结果是下面这个数,也就这一个。

899808641

抬头看路

反思整个过程,自己曝露出很多缺点。

有句话说心中有数,手上不乱。看到问题没有好好的分析问题,有什么解决方案,有多少,分析每个方案的特点、所能解决的问题。上来就凭感觉做,然后想大力出奇迹,简直是痴人说梦,事倍功半,过程中老感觉不踏实,那里怪怪的。那每种方案的复杂度是多少呢,能解决的问题能力多大呢?试除法的时间复杂度我起初一直错误的以为是 $O(n^{1.5})$,实际应该为 $O(n^{0.5})$,那其实是遍历区间内所有素数筛法的时间复杂度,而$O(n^{0.5})$ 才是 筛选一个数的时间复杂度。虽然感觉也怪怪的,但是没有细心的想想为什么感觉怪怪的。错误的时间复杂度估计,粗心大意,也是过于快放弃这种方案的原因。有句话还是挺有道理的,对感觉奇怪的地方进行深入的思考,查找资料求证,就可能会发现一些令人吃惊的与设想不同的结果。

其次,调试程序大意,主观臆断。代码没进行单元测试,试除法程序运行时间过长,没有具体分析原因就直接尝试第二种方案。

第三,偏离主目标,这是严重的路线方向问题。明显发现欧拉筛法行不通的时候,仍花费不少时间在上面,这个事情应该放到延迟重要的事情。

总结

对于这个事情的结果是,一个一小时内可以解决的问题终于在几个小时候后把问题解决了。顺利的进入了群,自豪骄傲。

参考

素性测试