#prime #primality #primality-test #number-theory #no-std

nightly no-std machine-prime

适用于机器整数的高效素性检验

6个稳定版本

1.3.0 2024年6月27日
1.2.2 2023年10月6日
1.2.1 2023年9月9日
1.2.0 2023年7月1日
1.0.0 2023年4月24日

#175 in 数学

Download history 8/week @ 2024-04-14 11/week @ 2024-04-21 11/week @ 2024-04-28 5/week @ 2024-05-05 16/week @ 2024-05-19 6/week @ 2024-05-26 8/week @ 2024-06-02 6/week @ 2024-06-09 14/week @ 2024-06-16 144/week @ 2024-06-23 34/week @ 2024-06-30 3/week @ 2024-07-07 10/week @ 2024-07-14 1/week @ 2024-07-21 51/week @ 2024-07-28

66 每月下载次数
用于 2 个Crate(通过 数论

CC0 许可证

1.5MB
17K SLoC

Machine prime是一个简单的64位整数素性检验,以可重复的方式构建,使用了F-Analysis库和Feitsma/Galway的2的底数伪素数表。它可以在crates.io上获得。

提供了两个具有C风格API的函数,以便在其他语言中调用。

  • is_prime
  • is_prime_wc (最坏情况)

is_prime针对平均情况进行了优化,并用作通用素性检验。is_prime_wc针对最坏情况进行了优化,并用于已怀疑为素数的数字的函数中。例如,在已经执行了试除法的因式分解中。它执行绝对最小的检查,并允许有少量已知的失败点,留给用户决定是否需要付出代价来检查它们。

此函数API将永远不会改变。is_prime将始终正确评估任何64位整数,但is_prime_wc的失败点可能会更改。

这些函数提供了三种模式,默认、小型和微型。随着每个后续模式的内存使用减少,复杂性增加。

默认模式使用大型散列表,并通过素数逆乘以进行试除法

  • is_prime复杂度:最坏情况2.23 * Fermat检验,平均情况0.28 * Fermat检验
  • is-prime_wc复杂度:最坏情况1.95 * Fermat检验,平均情况1.2* fermat检验
  • is_prime_wc失败:在0处恐慌,将1标记为素数,将2标记为合数
  • 由f-analysis的to_hashtable(Some(262144),Some(1276800789),Some(65535))构建散列表。计算到Feitsma表的EPF伪素数,并应用散列表方法来重现使用的散列表。请参阅f-analysis中的"散列表"示例以获取显式实现。
  • 总内存:526464字节

SSMR与默认值相同,但对于小于2^40的整数将分支到使用SSMR算法

  • 参数和失败情况与SSMR存储库相同
  • 由于分支、缓存利用和计算修改,它比SSMR存储库慢
  • 只有当SSMR存储库不提供足够大的区间时才使用此变体

Small省略了散列表,但仍使用试除法

  • is_prime复杂度:最坏情况2.8 * Fermat测试,平均情况<0.567 * Fermat测试
  • is-prime_wc复杂度:最坏情况2.5 * Fermat测试,平均情况<1.31 * Fermat测试
  • is_prime_wc失败:在0处恐慌,将1标记为素数,将2标记为合数,1194649和12327121无限循环
  • 除了最初的Fermat测试外,还使用修改后的Lucas序列测试

Tiny仅使用Small中实现的Fermat基,因此is_prime和is_prime_wc之间唯一的区别是后者省略了任何额外的检查以确保正确性。它比Small节省一小部分内存。

请注意,所有失败在调试模式下都将导致恐慌,但被优化覆盖,Makefile生成的动态库不会对任何情况恐慌。

用法

由于编译无标准库存在一些障碍,crates.io和存储库中的版本略有不同,尽管使用的是完全相同的算法。crates.io版本是为稳定的编译器配置的,而存储库是为夜间编译器配置的,因为目的是用它来构建动态库。

要从crates.io使用,只需在cargo.toml文件中包含它,并使用“small”或“tiny”功能(如果您想使用这些版本)。默认值将是最快的,具有散列表。

要作为动态库使用,请确保您正在运行rustc夜间版本; git clone此存储库并运行make以编译默认模式,make small以编译Small模式,make tiny以编译Tiny模式。这将创建库,并且make install将安装到/lib/libprime.so。 (确保您是超级用户)。安装库是推荐的,但不是绝对必要的。如果您使用gcc,请使用-lprime链接到它。

请参阅存储库中的"binding"文件夹中的各种语言绑定。支持包括Ada、C、Fortran、Julia和Python在内的几种语言。

目的

许多数论函数要么需要素性测试,要么使用素性测试以提高效率。例如,勒让德符号和分解。虽然素性测试很少是这些函数的瓶颈,但它是在高度优化的计算中的限制因素。通过提供一种快速的开源实现,该实现可以在许多语言和架构中调用,可以最小化构建此类函数的工作。

注意事项

此素性测试的目的不是在所有区间中都是最快的,而是在一般情况下更快,平均情况更快。有些小测试对于32位来说更快,然而这个区间如此之小,以至于为它们进行分支将导致总体效率降低。有关基准测试和与其他高效素性测试的比较,请参阅性能

存在一些用于优化内存的快速函数。然而,它们使用了浮点数运算。该库的目的是实现极高的速度,同时足够灵活,以便在只支持整数运算时也能使用。因此,没有使用浮点数运算、内联汇编和SIMD。此外,这也是为什么提供低内存版本的原因,因为并非每个人都能或愿意使用超过500千字节的内存。

二进制动态库的大小因编译器而异,但以下是一些合理的估计:默认-542.4kb,小型-18.1kb,微型-14kb

对于嵌入式系统的构建尚未经过测试,但尚未发现导致失败的原因。

此软件属于公共领域,所有值都可以使用开源的可审计的f-analysis库进行确定性重新计算。

无运行时依赖

功能