问题标签 [primality-test]

我使用了一些取自 Rosetta Code 的代码。我重命名了一些东西，但我并没有真正改变任何东西。

它与一些伪代码非常匹配。但是，当我测试数字时

123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901

它返回False。Miller-Rabin 的其他（python 和 java）实现返回True可能的素数。经过一些测试，仅回合后try_composite返回！我真的很想知道任何错误，我猜是缩进错误或我不知道的某些功能。True2

我知道米勒-拉宾素数检验是概率性的。但是，我想将它用于不留任何错误空间的编程任务。

long long如果输入数字是 64 位整数（即在 C 中），我们可以假设它是正确的吗？

我有下面显示的 Verilog 代码，如果我尝试编译它，我会收到一条错误消息。关键是我正在尝试操作输入，只要我知道在 Verilog 中无法完成。关键是我需要在 Verilog 中检查以下条件：

目前我有以下代码：

另请注意，我需要以 6n+1 或 6n-1 的形式测试素数，并且我还需要在我的代码中假设 0 和 1 也是素数。

如果我尝试上面的代码，我会收到一条错误消息：

未为 verilog 启用增强的 FOR 循环

如果有人可以帮助我解决错误并在 Verilog 中完成我的逻辑，我会很高兴。

我在 Haskell 中实现了 Miller Rabin 测试。我试图严格遵循米勒拉宾测试的维基百科条目中给出的伪代码。现在我在网上发现，对于某些证人的选择，测试在一定的给定范围内是确定性的。我对 2^64 以下的素数感兴趣，所以我在这篇文章中找到了足够的界限。 我需要哪些见证人来进行 Rabin-Miller 测试以获取高达 10¹⁸ 的数字？. 但是，该代码似乎适用于我测试过的大多数小质数，但对于一些较大的质数却失败了。例如，我尝试了十位素数 5915587277，测试返回 false。我认为我的实现是正确的，但希望有人能发现我在哪里犯了错误并误解了关于 MR 测试的一些内容。提前感谢您的帮助。另外，对于看起来凌乱的代码感到抱歉。

我正在尝试计算输入是否为质数但出现问题......这是我的代码：

它false每次都给我。有人对我做错了什么有任何线索或想法吗？

我在 F# 中的质数检查器遇到了一些问题。它似乎没有给出正确的结果，所以我猜我在某个地方搞砸了逻辑，但我不知道在哪里。该实现是一种简单的暴力破解，因此逻辑并不复杂，而且我之前在命令式语言中使用 for 循环实现了类似的解决方案。

所以我需要解决一个问题，找到验证以下内容的第 n 个数：它是两个连续素数的和，它给出一个整数平方根。我的问题是，eratosthenes 的筛子使用了太多的内存，而对素数的天真检查太慢了。有什么方法可以快速解决这个问题并且没有额外的记忆？我尝试使用费马定理，但结果速度较慢。

提前致谢。

我正在编写一个程序来演示 Java 中的 Miller-Rabin 概率测试。代码基本完成了...

我已经硬编码 86 作为我的值来证明我的问题。通过将 a 提高到 m 并取模数 n 第一次计算 b 的地方，数学是不正确的。而不是给出 86 的 b0 是 86^19 % 153 的正确答案，而是给我 b0 等于 107。我已经在调试器中检查了我的值，它们是正确的。我还检查了 a^m 的值，它给了我 86^19 所以问题出现在模数部分。不幸的是，我不知道是什么让数学失败了。

我用python写了两个素数测试。第一个是基于试验划分，第二个是埃拉托色尼筛。我的理解是 sieve 的时间复杂度应该比 Trial 小，所以 sieve 应该渐近更快。

但是，当我运行它时，试用分区要快得多。例如， when n = 6*(10**11),is_prime(n)花费不到一秒钟，但is_prime_sieve(n)实际上永远不会结束！我是不是把筛子写错了？

我的代码是：

我们知道所有素数的形式都是 6k+-1。要检查 n 是否为素数，我们不能将 n 除以 6，取其下限，然后检查加或减 1 是否等于 n？那将检查一个数字是否在恒定时间内是素数，对吗？如果这是真的，为什么其他方法会费心使用筛子进行素性测试？另外，使用这种方法，找到从 2 到 n 的素数范围不会是 O(n) 吗？那么这种方法比埃拉托色尼筛法快吗？