问题标签 [primality-test]

我在互联网上找到了这个解决方案，我需要一些帮助来理解它：

有几件事：

我的理解是，如果折叠函数的累加器是 aBoolean它必须在 lambda 函数本身中设置。就像是：

但这里不是这样。

此外，用于的范围primes没有终止编号。我知道这行得通的原因是因为 Haskell 的懒惰评估，但它到底是如何工作的呢？

最后，这个函数似乎不会返回正确的布尔值。素数是除自身和 1 之外没有其他除数的数。所以 lambda 不应该这样读：

我彻底糊涂了。请帮帮我。

我试图在 Java 上实现 Miller-Rabin 素数测试，并将其计算时间与BigInteger类的本机素数测试进行对比。鉴于我在这里，您可能已经猜到我的代码不起作用。问题是，我得到的错误是Lady Math 说不可能的。我想知道我做错了什么。

米勒-拉宾素数检验背后的想法是，所有素数都满足一个适当性。如果不满足该适当性，则该数字是合数；但是，如果满足适当性，则该数可能是素数，也可能属于称为伪素数的合数的子集。绝对不可能发生的情况是质数被测试识别为合数。
这正是运行我的代码时有时会发生的事情。

我在我的代码中搜索数学错误，我认为没有。我尝试搜索 Java 错误，但没有找到。显然有一些东西（或很多东西）我没有看到，所以我想寻求帮助。

下面是main一个静态类，它只是为了容纳 Miller-Rabin 测试的实现而创建的，它在main. 这不是概率测试，而是确定性测试：该方法搜索所有可能的证人，如果找到，则返回false（即不是素数）；否则返回true。

编辑：以下几行是方法log(x,base)。

在 Wikipedia 上，下面的算法应该通过概率 Rabin-Miller 素数测试来测试奇数 n 是否是复合数。

我在下面GitHub 上的 BigIntANSForth中的算法实现可能是错误的。前缀“b”代表“大”；有一个大数字的参数堆栈和一个额外的大数字堆栈'bx'。'ys' 也是一个单元格整数的额外堆栈。

条形前缀代表“巴雷特缩减”。

83568136581357135713573105731571385713857130571301111111111111111111111112429 是由于实现任何精度的复合，但由于Wolfram Alpha是素数。

我不确定我是否正确解释了算法。有什么建议吗？

欢迎。我正在尝试实施 MillerRabin 测试来检查给定的大数是否是素数。这是我的代码：

它适用于小型 Bigintegers。但是如果我的程序需要计算超过 16 位的数字，程序就会冻结。例如，在成功检查数字是否为素数后，程序突然没有响应。我不明白这怎么可能。如果它检查了一个大数字，那么再次检查另一个应该没有问题。甚至调试器也没有帮助，因为 step options消失了。如果需要，我可以分享更多功能代码。上述功能对于小数字正常工作。

编辑。更改 BigInteger.ModPow 的模函数有帮助。不幸的是，现在对于更大的数字，超过 3000 位它永远不会返回质数，这是相当不可能的。还是真的很难找到 prme 号码？

我正在尝试制作 RSA 算法。为此，我需要 rabin-miller+witness+模幂（至少我需要使用它）。当我生成随机数以检查它们是否是素数时，问题就出现了，结果是非素数是 rabin-miller 算法的素数。有人可以帮我看看我失败的地方。提前致谢。

下面是一段代码，它显示了一个输出，说明用户输入的数字是否为质数。

上面写的这段代码不是我的，它每次都成功地识别出一个素数（即打印else子句的printf语句）。

我对 if 语句的理解是if -else语句中的else子句属于最近的if语句，它还没有else子句。因此，话虽如此，我相信上面这段代码中的else子句属于最近的if语句。

我的问题是：如果用户输入像 31 或 37 这样的素数或任何其他素数，else子句的printf语句如何打印？考虑到 b 只会递增到，条件（第二个if语句的）将始终为真。所以如果用户输入数字 31，变量b只会增加到 30。不应该是打印第二个if语句的printf语句，不管用户输入的数字是否是素数与否，考虑到条件将始终为真？if (b<a)(a-1)if (b<a)

上面的代码如何正确打印所有素数，从而正常工作？（根据我对if语句工作方式的有限理解，它不应该）

最近对简单的素性测试感兴趣。我有以下两个函数，它们返回给定输入之前的所有素数列表。我制作的第一个，另一个是基于维基百科的素性测试伪代码。然后，我将我的稍微修改为我认为最接近维基百科的。

当我给它们计时（输入/限制为 10000）时，我的时间比另一个长一个数量级。我不太清楚为什么，至于我，他们正在做非常相似的事情。我的检查一个带有“any”的素数列表，而wiki检查这些相同的数字，但使用while循环生成它们。我错过了什么？

def 重复（m，结果，a，s，d）：

我需要编写一个素数测试 python 程序来测试非常大的数字，比如至少 100 位数字。上面的代码是 Miller Rabin 确定素数测试重复平方的代码的一部分。对于大量数据，它的工作速度非常慢。我怎样才能加快速度？这是为了一个项目。谢谢！

Miller-Rabin 检验使用k个随机整数来检验素数。

根据 CLRS，第 3^版，第 971 页：

定理 31.38

如果 n 是一个奇合数，那么见证 n 的复合性的人数至少为 (n - 1)/2。

那么我们为什么不直接运行k 次随机测试，而是使用不同的(n - 1) / 2 值并测试它们的素数呢？由于除了 2 之外的所有素数都是奇数，并且没有见证人至少是 (n - 1) / 2，因此我们保证如果存在就可以找到见证人。

我正在学习试验划分素数测试的基础知识，因此，在代码中实现它。可以使用许多技巧来提高算法的性能，例如：

1) 仅将试验除法运行到平方根 (n)

2）通过创建一个直到平方根（n）的筛子来用内存换取时间，然后只在创建的筛子中的素数上运行试除法

n%6但是，如果发现 (n mod 6)的值1 or 5（使用 6k +/- 1 规则），我没有找到将结果作为复合返回的想法。在我们的素数确定测试中使用这个规则不会提高它的性能吗？如果是，为什么没有在任何地方提到它？如果不是，为什么会这样？

谢谢。