每天学一点Python之NumPy基础11质因数

off999 2024-12-11 16:24 24 浏览 0 评论

质因数 (http://en.wikipedia.org/wiki/Prime_factor) 是指正好整除一个整数而不留余数的质数。对于大数来说，寻找质因数几乎是不可能的。

因此，质因数在密码学中得到了应用。然而，使用正确的算法--费马因式分解法（http://en.wikipedia.org/wiki/Fermat%27s_factorization_method）和 NumPy--对于小数来说，因式分解变得相对容易。

其原理是根据下式将一个数 N 分解成两个数 c 和 d：

我们可以递归地应用因式分解，直到得到所需的质因数。

这需要四个步骤，让我们来看看是如何完成的。

算法要求我们对 a 的值进行多次试验。

首先我们将创建一个包含试验值的数组。创建一个 NumPy 数组可以省去循环。

不过，在创建数组时要注意，不要创建占用内存过大的数组。在我的系统中，一百万个元素的数组大小似乎恰到好处：

a = np.ceil(np.sqrt(n))
lim = min(n, LIM)
a = np.arange(a, a + lim)
b2 = a ** 2 - n

我们使用 ( ceil ) 方法按元素顺序返回输入值的上限。

第二步 获取 b 数组的小数部分。现在我们要检查 ( b ) 是否是正方形。使用名为 ( modf ) 的 NumPy 方法来获取 ( b ) 的小数部分。

数组的小数部分：

fractions = np.modf(np.sqrt(b2))[0]

第三步 查找 0 分数。调用 ( where ) NumPy 方法查找零分数的索引，其中分数部分为 0：

indices = np.where(fractions == 0)

第四步 找出第一个出现的零分数。

首先，使用上一步的索引数组调用 NumPy 方法 ( take )，获取零分率的值。然后使用 NumPy 方法 ( ravel ) 将数组网格化：

a = np.ravel(np.take(a, indices))[0]

这一行有点复杂，但确实展示了两种有用的方法。如果写成

a = a[indices][0]

在本节中，我们应用了一组有用且有趣的 NumPy 方法，这些方法的说明如下：

Method Name	Method Description
ceil()	计算数组元素的上限（参见 http://docs.scipy.org/doc/numpy/reference/generated/numpy.ceil.html）
modf()	返回浮点数的小数部分和积分部分（参见 http://docs.scipy.org/doc/numpy/reference/generated/ numpy.modf.html）
where()	根据条件返回数组索引（参见 http://docs.scipy.org/doc/numpy/reference/generated/numpy.where.html）
ravel()	返回一个扁平化数组（参见 http://docs.scipy.org/doc/numpy/reference/generated/numpy.ravel.html）
take()	从数组中提取元素（参见 http://docs.scipy.org/doc/numpy/reference/generated/numpy.take.html）