米勒拉宾

我将这种快速（参见性能）、确定性（最多 64 位无符号）、许可许可 (MIT) Miller-Rabin 素数测试作为 Python 的 C 扩展来实现，因此您不必这样做。

仅支持 CPython 3.6 或更高版本。

项目规范网址：https ://github.com/zmwangx/miller-rabin

• 算法
• 安装
• API
• 表现
• 发展
• 贡献

算法

该库实现了 [2] 推荐的针对 64 位无符号整数的 Miller-Rabin 素数测试的 Bradley Berg 确定性变体 [1]，以及针对超过 64 位的整数的通常概率测试。具有小素数除法的初步测试和在某些情况下通过一次费马测试的灵感来自boost::multiprecision::miller_rabin_test[3]。直接对照查找表检查 16 位内的整数。

GMP[4] 用于模幂运算，因此库链接到 libgmp (LGPLv3)。

信用：

• [1] https://www.techneon.com/（许可许可证，请参阅COPYING.techneon）
• [2] https://miller-rabin.appspot.com/
• [3] https://www.boost.org/doc/libs/release/libs/multiprecision/doc/html/boost_multiprecision/tut/primetest.html（Boost软件许可证，请参阅COPYING.boost）
• [4] https://gmplib.org/（LGPLv3，见COPYING.gmp）

安装

pip install miller-rabin

适用于 Python 3.6、3.7 和 3.8 的 macOS 和 Linux（ 和 ）manylinux1可manylinux2010使用包含依赖项的轮子。manylinux2014一个相当新的 pip 应该能够自动选择一个轮子（manylinux1在 v8.1.2 中添加了支持），但建议将 pip 更新到最新。

要从源代码分发版安装，需要 CPython 开发头文件以及libgmp开发头文件。

API

API 非常简单，因此不需要单独的 Sphinx 文档站点。

NAME
    miller_rabin - Fast, deterministic* Miller-Rabin primality test.

FUNCTIONS
    miller_rabin(n, k=10, /)
        Perform Miller-Rabin primality test on the arbitrary precision int.

        A deterministic variant is auto-selected if n fits into 64-bit unsigned;
        otherwise, the probablistic variant is used, and k determines the number of
        test rounds to perform.

    miller_rabin_deterministic32(n, /)
        Perform deterministic Miller-Rabin primality test on the 32-bit unsigned int.

    miller_rabin_deterministic64(n, /)
        Perform deterministic Miller-Rabin primality test on the 64-bit unsigned int.

在实践中，您应该简单地miller_rabin对所有数字使用该函数，而不考虑位数，除非您想在不事先检查的情况下强制执行位数。

表现

TL;DR：这个库可以在 3.7GHz Intel Core i5 CPU（单线程）上每秒确定性地测试约 250 万奇数 64 位无符号整数。

下面是这个库的素数测试与gmpy2（Python 绑定到GMP）的一些基准测试。第一列是每个随机样本的位数（给定范围内的随机奇数），结果以每秒百万次测试为单位，根据大小为一百万的随机样本的总运行时间估计。标记的结果MR来自miller_rabin.miller_rabin该库；标记的结果G(25)适用gmpy2.is_prime于默认设置（25 轮）；标记G(10)为gmpy2.is_prime10 轮的结果（与此库对 64 位以上数字的默认值相当）。请注意，在引擎盖下gmpy2.is_prime使用。mpz_probab_prime_p详情请参阅bench/benchmark.py。

#bits	MR	G(25)	G(10)
1-32	4.538	0.901	1.581
32	4.553	0.916	1.601
1-64	2.597	0.845	1.377
64	2.500	0.755	1.258
65	1.120	0.694	1.153
96	1.044	0.642	0.977
128	0.832	0.495	0.745
256	0.327	0.204	0.286
(unit: million tests per second)
(CPU: Intel(R) Core(TM) i5-9600K CPU @ 3.70GHz)

#bits	MR	G(25)	G(10)
1-32	3.275	0.960	1.530
32	3.288	0.982	1.561
1-64	2.026	0.865	1.315
64	1.933	0.743	1.176
65	0.915	0.727	1.129
96	0.878	0.680	0.983
128	0.663	0.507	0.735
256	0.258	0.180	0.254
(unit: million tests per second)
(CPU: Intel(R) Core(TM) i7-8700B CPU @ 3.20GHz)

（所有基准测试都是单线程的。）

正如我们所看到的，这个库比 gmpy2快 50-200% ，此外它对无符号 64 位整数具有确定性，具体取决于 CPU。对于刚刚超过 64 位的整数，根据 CPU，这个库可能比gmpy2.is_prime10 轮慢 20%，但随着数字变大，差距会缩小，最终这个库会再次更快。

请注意，对于 64 位无符号整数，有一个纯 Python 实现alt/miller_rabin.py作为演示（实际上，它仍然使用 gmpy2 的mpz类型进行模幂运算，因此严格来说它不是纯 Python；原因是 CPython 的速度可能比 CPythonlong_pow慢 20 倍以上） GMPmpz_powm甚至只适用于无符号 64 位整数）。它比这个库慢得多，所以确实需要一个 C 扩展。

发展

参数处理代码由Argument Clinic从最新的 v3.6.x 发布树自动生成（为了兼容性）。

$ cd /path/to/cpython/dev/tree
$ git checkout v3.6.x
$ python3 Tools/clinic/clinic.py -f /path/to/miller-rabin/src/miller-rabin.c

贡献

欢迎投稿。算法更改应展示可衡量的性能改进（使用bench/benchmark.py）。

想法：

• 也许蒙哥马利乘法实现可能比mpz_powm？Perl 的 Math::Prime::Util 实现了蒙哥马利乘法montmath.h并将其用于 Miller-Rabin，但该实现是在 x64 asm 中实现的，我对此并不满意（尽管可能是必要的），不幸的是代码是 GPL。

• 我不太热衷于弄清楚 Windows 上的静态轮子构建，因此这里欢迎经验丰富的 Windows 开发人员的贡献。见.github/workflows/build-and-publish-distributions.yml。