问题标签 [primality-test]

我是Scheme的新手。我已经尝试并使用 PLT Scheme 实现了 Rabin-Miller 算法的概率变体。我知道这是概率性的，但我大部分时间都得到错误的结果。我用 C 实现了同样的东西，而且效果很好（从来没有失败过）。我在调试时得到了预期的输出，但是当我运行时，它几乎总是返回错误的结果。我使用了来自Wikipedia的算法。

另外，我是否在 Scheme 中以正确的方式编程？（我不确定我使用的循环部分的中断call/cc。我在某个网站上找到了它，从那以后一直在使用它。）

提前致谢。

我目前正在阅读 Doets 和 Van Eijck 所著的《通往逻辑、数学和编程的 Haskell 之路》一书。在这本书之前，我从未接触过任何函数式编程语言，所以请记住这一点。

在本书的早期，它给出了以下素数测试代码：

ldp 调用 primes1，调用 prime，再调用 ldp，这似乎是一个循环编程。虽然这本书确实提供了这个作为程序执行和终止原因的解释：

ldp 调用 primes1，即素数列表。这是“惰性列表”的第一个示例。该列表称为“惰性”列表，因为我们只计算列表中需要进一步处理的部分。要定义 primes1，我们需要对素数进行测试，但该测试本身是根据函数 LD 定义的，该函数又引用 primes1。我们似乎在绕圈子跑。通过避免 2 的素数测试，可以使这个循环变得非恶性。如果给定 2 是素数，那么我们可以在 LD 中使用 2 的素数来检查 3 是否为素数，依此类推，我们就成功了并运行

虽然我认为我理解这个解释，但如果有人能用外行的话解释一下，我将不胜感激：

1. 什么是“惰性列表”以及它在这种情况下如何应用？
2. 知道 2 是素数如何使程序不具有恶意？

非常感谢任何答案。

作为我自己的练习，我正在实施 Miller-Rabin 测试。（通过 SICP 工作）。我理解费马的小定理，并且能够成功地实现它。我在 Miller-Rabin 测试中被绊倒的部分是这个“1 mod n”业务。1 mod n（n是一些随机整数）不是总是1吗？所以我对“1 模 n 的非平凡平方根”可能是什么感到困惑，因为在我看来，“1 mod n”在处理整数值时始终为 1。我错过了什么？

所以我设计了以下函数来查看给定数字是否是 Haskell 中的素数（它假设第一个素数是 2）：

即使它可以被几个数字整除，它也有继续评估的明显缺陷:(。当它使用列表推导找到多个解决方案时，是否有任何理智的方法可以“削减”评估？

另外，您会尝试哪些其他实现？我不是在这里寻找性能，我只是想看看是否还有其他更“haskellish”的方式来做同样的事情。

为了检验一个数是否是素数，为什么我们必须检验它是否只能被该数的平方根整除？

我正在阅读有关主要测试算法的信息，并找到了AKS primality test。这个算法可以在Scheme或 C++ 中实现吗？

有没有人尝试实施 AKS 测试？

我想对大数实施米勒拉宾素性检验。我想知道如何在 C++ 中处理如此庞大的数字。我应该编写任何特殊函数来存储和处理这些大数字还是自动处理？

我有一些 10 ^N + K 形式的数字，其中 N 约为 1000，而 K 非常小（低于 500）。我想测试这些数字的素数。目前我正在使用以 2 为底的费马检验，然后检查小因素（<10000）。

但是，就我的目的而言，这相当慢。有比这更快的算法吗？能以某种方式利用这种特殊形式吗？

另外，如果两个数字仅在 K 上有所不同，是否可以更快地测试这两个数字？

我正在寻找一种算法来测试大（如 10 ²⁰⁰）数字。有什么好的算法吗？

理想情况下，我更喜欢不是概率的算法。

注意：数字有超过 50 位且少于 200 位的数字。

这是一个“真正的”任务吗，可以用任何语言编写（例如 C/C++）

那么，我的任务是“生成”长度超过 50 位（最大值 = 200）的随机数？

然后，我必须在素性测试中检查这个数字。

那么，这个任务是“真实的”吗？它会消耗多少时间/资源？

另一种方法是从特殊类（可以使用哪个类？）中生成素数 Mersenn 数或其他数