质因数是可以整除某个整数的质数。通过寻找质因数的方式破解密码看似几乎不可能,但如果使用正确的算法——Fermat因式分解法和NumPy,这将变得很容易。基本思路是使用如下公式把整数N分解为c和d两个数:
递归地应用这个因式分解法,直至得到需要的质因数。
具体步骤
该算法需要我们为上述公式中的a
尝试选择若干取值。
- 创建尝试值数组。
创建一个NumPy数组,避免使用循环语句,这是一个合理的做法。但要注意,不能创建太大的、消耗内存太多的数组。在我用的系统中,使用包含一百万个元素的数组看似是没问题的。
这里使用ceil
函数对其输入参数的数组元素向上取整。
- 得到数组
b
的小数部分。
b = numpy.sqrt(b2)
我们将检查数组b2
中的元素是否是某个整数的平方。使用NumPy中的modf
函数,可以获得数组b
的小数部分。
- 查找小数部分为0的数组元素。
使用NumPy中的where
函数,获得数组fractions
中取值为0的元素的索引值。
- 找到第一个小数部分为0的数组元素。
实际上,我们只需要第一个小数部分为0的数组元素。首先调用NumPy的take
函数,把上一步骤得到的数组indices
作为参数,获得数组a
中小数部分为0的数组元素。然后需要使用NumPy的ravel
函数,把得到的结果展开为一维数组。
如果需要解决的问题是查找数字600851475143的最大质因数,完整代码如下。
这段代码的执行结果如下。
小结
我们采用了递归的方式应用Fermat因式分解法,用到了NumPy中的ceil
、modf
、where
、ravel
和take
函数。这些函数的功能描述如下。
函数 | 功能描述 |
---|---|
ceil |
对数组元素向上取整 |
modf |
返回浮点数的小数部分和整数部分 |
where |
返回取值符合条件的数组元素的索引值 |
ravel |
返回一个展开的一维数组 |
take |
从数组中取出指定的元素 |