利用Miller-Rabin素数测试与Pollard rho算法实现shell中的factor指令

作者: shad0w_walker(admin) 分类: 算法 发布时间: 2016-08-17 22:08 ė 6 没有评论

什么是factor指令

factor即分解质因数——输入一个数字,快速分解质因数。

具体的运行结果见后文展示

 

起因

众所周知,Ubuntu的shell中自带factor指令,它能够对极大的整数快速分解质因数,分解质因数本不足为奇,但其强大之处正如我所说——极大、快速。可是这个指令,在osx上没有呀!于是我决定自己用python写一个。

 

实现方法一:暴力试除

naive的我决定写一个暴力分解的程序,即从2到\(\sqrt{n}\)枚举素因子。因为将n分解到1后就能跳出循环,所以对于很多合数并不会达到最坏的算法复杂度\(O(\sqrt{n})\),有些看上去特别大的数依然分解得很快。可是遇到素数就GG了啊。

点击此处展开代码

以上的这段代码是很久以前写的python脚本,注意是python2

使用方法(仅针对新手):

将这段代码保存,例如路径为~/factor.py,然后赋予此文件可执行权限,执行

chmod +x ~/factor.py

接着给指令添加别名,在~/.profile中加入一行

alias factor=’~/factor.py’

重启shell,factor指令就能够使用了。

仿照Ubuntu中的factor,这段脚本有两种使用方法,一是直接factor+需要分解的数(可以是用空格分隔的多个数),二是执行factor,每次分解一个数,具体见图。

 

factor_description

 

实现方法二:太长不想再打一遍,见本文标题

随着对质因数分解的进一步了解,我发现暴力试除的做法实在是速度太慢,逼格太low啦。

Miller-Rabin素数测试:快速判断一个数是否为素数的近似算法(伪素数测试)

Pollard rho algorithm:Pollard的rho启发式方法,快速分解质因数的算法

这两个算法在《算法导论》的第31章:数论算法(章节31.8和31.9)中有详细的介绍,包括算法的过程、实现方法、数学论证等等。

值得一提的是Miller-Rabin素数测试理论上并不能100%判断出质数,极小概率下会将合数判定成素数。但是可以通过多次选取不同的基来降低出错概率,使其变得极其微小。关于Miller-Rabin素数测试的出错概率,看《算法导论》去……

其实参加ACM-ICPC的话,并不会对Miller-Rabin素数测试陌生,以下这段代码,从裤裆里掏出ACM的模板,把C++翻译成python就行啦,至于为什么不用C++写,因为python在大数的运算上比C++好用多了。

点击此处展开代码

这段代码是python3,别问我为什么上次用python2这次用python3……

配置方法和上面的相同,记得在~/.profile中加入这句话

alias factor=’~/factor.py’

 

方法二真的是快的飞起,对一般的大数,基本是秒分解。Pollard rho算法本身就决定了一个数如果有多个小素数因子,就能大大提高分解速度,所以,依然有很多数在分解时效果不好,例如5316911983139663487003542222693990401这个数,运行很久都不能出解。

不过总体来说,这已经比暴力试除的做法高到不知道哪里去了。

本文出自shad0w_walker,转载时请注明出处及相应链接。

本文永久链接: https://www.sdwalker.com/archives/502.html

发表评论

电子邮件地址不会被公开。 必填项已用*标注

返回顶部