22

我刚刚实现了Miller-Rabin-Test和一个用于分解数字的简单函数。两者都可以做得更好，至少 Miller-Rabin-Test 是众所周知的。

那么您能否告诉我是否存在实现此类常见素数函数的 Python 库，或者为什么不存在此类库？

4

6 回答 6

23

我刚刚isprime从SymPy包中发现：

import sympy
print sympy.isprime(10)

输出：

False

不要与 混淆prime，它返回第 n 个素数：

import sympy
print sympy.prime(10)

输出：

29
于 2014-08-29T16:59:47.627 回答
14

gmpy2支持各种伪素数测试。Miller-Rabin 检验可作为gmpy2.is_strong_prp().

gmpy2 还没有任何分解代码。

免责声明：我是 gmpy2 的维护者。素数测试基于来自http://sourceforge.net/projects/mpzprp/files/的代码

于 2012-06-11T05:34:33.570 回答
3

我不认为标准库中存在这样一个专门用于素数函数的模块，但当然有很多人编写过素数测试等。

一个面向多精度算术的is_prime()库next_prime()是GMPY2. 该文档也可用。

于 2012-06-11T05:34:07.643 回答
2

如果您正在寻找算法的实现，请查看Rosetta Code。该网站有许多 Python 实现。您绝对可以根据个人需要拼凑自己的图书馆。

于 2012-06-11T05:36:49.543 回答
0

Primes-Library-Python是一个开发中的 Python 库。适用于基本功能，对于较大的数字非常快。

于 2014-10-28T17:08:39.620 回答
0

我创建了一个包含许多功能的库（请参阅自述文件），但最重要的是它包含 Alpertons ECM 库，因此您可以使用 ipython3 中的 Alperton 引擎（即使在 Android 下的 Termux 下）：

https://github.com/oppressionslayer/primalitytest/

只需观看 README 开头的视频，看看使用 Alperton 的 C 库是多么容易。

要使用它，只需使用 from sfactorint import p2ecm from the primality 目录。要访问 Alperton 的 ECM，请执行以下步骤：

cd calculators
make
cd ..

就是这样，sfactorint 然后使用 Alpertons ECM SIQS 进行分解。我计划制作一个自动执行 make 步骤的 pip 安装，所以如果你对它感兴趣，请继续关注。

这是一个 60 位数字因子的样本，我在视频中的 Android 上以大致相同的速度执行相同的操作：

In [22]: import time   
    ...: start = time.time()   
    ...: print(p2ecm(632459103267572196107100983820469021721602147490918660274601))   
    ...: end = time.time()   
    ...: print(end-start)    
    ...:                                                                                                                                                       
[650655447295098801102272374367, 972033825117160941379425504503]
5.197108030319214
于 2020-07-01T23:19:32.550 回答