素性测试二进制

Question

我正在使用 Java 程序 (BigIntegers) 生成数字，我想知道是否有一个现成的二进制文件可以用来对生成的数字运行素性测试......假设我通过来自我的 Java 程序的管道馈送它们进入二进制。它在那里吗？我正在尝试在 apt 上找到 aks 的软件包，但我看不到任何“直接”的东西，只有我可以用来编程东西的库（例如，基于 GMP）。

Answer 1

openssl

程序 openssl 进行素性测试：

$ a=31
$ openssl prime 31
1F (31) is prime

$ openssl prime 18446744073709551557      
FFFFFFFFFFFFFFC5 (18446744073709551557) is prime

该命令与帮助 ( openssl help)一起列出：

$ openssl help 2>&1 | grep prime
pkeyparam         pkeyutl           prime             rand

实际命令的详细信息由 (-help或--help)给出：

$ openssl prime -help
Usage: prime [options] [number...]
  number Number to check for primality
 -help         Display this summary
 -hex          Hex output
 -generate     Generate a prime
 -bits +int    Size of number in bits
 -safe         When used with -generate, generate a safe prime
 -checks +int  Number of checks

很长的数字也是可能的 (2^521)-1（具有 157 个十进制数字的梅森数）：

$ time openssl prime $(BC_LINE_LENGTH=0 bc <<<'2^521-1')
1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
(6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151)
is prime

real    0m0.042s

其他两个未连接到 openssl 但与素数相关的实用程序是：

素数和因数：

素数 - 在范围内生成素数 factor - 因子数

$  echo $(primes 10 50)
11 13 17 19 23 29 31 37 41 43 47

$ openssl prime 11 13 17 19 23 29 31 37 41 43 47
B (11) is prime
D (13) is prime
11 (17) is prime
13 (19) is prime
17 (23) is prime
1D (29) is prime
1F (31) is prime
25 (37) is prime
29 (41) is prime
2B (43) is prime
2F (47) is prime

$ factor 11 13 17 19 23 29 31 37 41 43 47
11: 11
13: 13
17: 17
19: 19
23: 23
29: 29
31: 31
37: 37
41: 41
43: 43
47: 47

$ factor 18446744073709551557
18446744073709551557: 18446744073709551557

$ factor 18446744073709551559
18446744073709551559: 41 163 269 8807 1165112831

非常接近最大（有符号）64 位整数：

$ printf '%X\n' 18446744073709551559 $(( (2<<63) - 1 ))
FFFFFFFFFFFFFFC7
FFFFFFFFFFFFFFFF