问题标签 [primality-test]

我正在尝试调试标准（即概率）Miller-Rabin 测试的实现。这是现在的代码，在方法中执行了基本的测试main：

我目前遇到的问题是：最后两个测试返回错误，这（因为它们都是素数）应该是不可能的。即使我通过了尽可能多的测试，is_prime仍然输出错误。

在这一点上，我真的不知道出了什么问题。有任何想法吗？

我正在尝试在 SAGE 中编写 Miller-Rabin 素数测试。这是我的代码：

它适用于不太小的数字，但是对于 n=3847982374893247238947238473289472348923784923748723482374832748923748932478239472389478239479273 我得到“3207”至多 947523。我会感谢任何建议:)

以下代码用于质数。我想知道为什么我们i<=n/2在循环中使用条件。

C程序：

我写了 isPrime 函数。它检查给定的数字是否为素数。最后一个“主要”列表是单独给出的。

我认为如果可能的话，将两个函数合并为一个总是更好。所以我将 isPrime 和 prime 合并为一个函数 isPrime2。但是isPrime2的性能很差。

是素数 40000000000000000001

=> 0.5 秒

isPrime2 400000000000000000001

=> 19.8 秒

我的机器是 Ubuntu 17.10 x86-64。我正在使用 ghc 8.2.1。有谁知道为什么？

所以我试图找到 10,001 个素数。是的，它是 euler #7 问题。我写的代码似乎给了我从 3 到 10,001 的所有素数，但我的答案仍然不正确。我知道还有其他关于此的问题已经得到解答，但窃取别人的代码并不能帮助我学习。所以我正在寻找我在哪里出错的洞察力。首先，我分离出所有奇数并将它们添加到列表中。我注意到列表中有一些素数的平方，所以我对照从 2 到 10,0001 的每个数字的平方检查列表。那应该只给我留下素数，但我仍然得到错误的答案。任何想法都会很棒谢谢

我一直在尝试从头开始实施 Miller-Rabin 素数测试（仅适用于 64 位整数（长整数））。我已经尝试过来自Wikipedia以及其他各种网站的 Java 和伪代码。到目前为止，只有非常少的数字能够正常工作。大多数数字都被错误地标记为复合数字，例如 53 或 101。我尝试跟踪代码的各个部分以查看问题所在。它似乎在最里面的循环中。我不知道具体是什么问题。任何帮助表示赞赏。谢谢！

这是我的代码：

我已经实现了以下两个函数来确定 n 是否是 fermat 素数（如果它为真则返回 n，如果不是则返回 -1），但它总是返回 -1，无法弄清楚为什么（gc 是一个函数 taht 计算gcd)

以下程序找到给定数 n 的最小整数除数（大于 1）。它以一种直接的方式做到这一点，通过测试 n 是否可以被从 2 开始的连续整数整除。

我们可以如下测试一个数是否为素数：n 是素数当且仅当 n 是它自己的最小除数。

find-divisor 的最终测试基于这样一个事实，即如果 n 不是素数，则它必须有一个小于或等于 n 的除数。44 这意味着该算法只需要测试 1 和 n 之间的除数。因此，将 n 识别为素数所需的步骤数将具有增长顺序 (n)。

我还有另一个回溯挑战，其中我必须得到所有可能的素数组合，这些组合加起来是一个特定的数字。我已经使用Wikipedia中的通用算法完成了任务，但是对于数字 100，运行了一个多小时，到下课时还没有完成。我想知道：记忆化（你怎么拼写？）会显着提高算法的性能（比如，它会不会让它明显更快）？我正在使用 c++，并且该函数被调用了很多次。我正在使用递归回溯，我似乎记得对于简单的问题大约是 O(n!)。

这个问题实际上可能与 Miller-Rabin 素性测试程序无关；它可能只容易分析一些简单的伪代码。

在 CLRS (Introduction to Algorithms 3ed) 的第 969 页，介绍了 Miller-Rabin 的辅助函数：

我完全从教科书中复制了以上内容。

现在，只知道MODULAR-EXPONENTIATION返回 0 和 n-1 之间的结果，包括在内，我认为上面的伪代码完全等同于

如果是这样，那么原始实现可能还有其他问题，因为如果我没记错的话，Miller-Rabin 见证确实需要某种循环。有人可以提供一个简单的反例来证明我错了吗？