问题标签 [primes]

我正在玩耍并尝试编写 RSA 的实现。问题是我一直在生成大量质数，这些质数涉及生成密钥对。有人能指出一种快速生成巨大素数/可能素数的方法吗？

我正在寻找想法/代码（最好是 C#，但其他语言也可以）来创建无限大的 Ulam 的 Spiral（受程序运行时间长度的限制，或直到停止）。

现在这些数字都是素数，所以它们的代码是无关紧要的。有趣的部分是如何对不断增长的（无限）螺旋中的排列进行编码，什么样的数据结构可以很好地支持它，以及输出的想法（图形文件，文本文件？）。

你会怎么做？

我编写了以下程序来对一个数字进行质因数分解：

以下是我得到的输出：

Altho'，返回值被正确打印，之后的返回值似乎一直没有打印。我错过了什么？

另外，如何改进程序（继续使用递归）

我的问题是(g^x) mod p在 JavaScript 中快速计算，^取幂mod是模运算。所有输入都是非负整数，x大约有 256 位，并且p是 2048 位的质数，g最多可以有 2048 位。

我发现的大多数可以在 JavaScript 中执行此操作的软件似乎都使用 JavaScript BigInt 库（http://www.leemon.com/crypto/BigInt.html）。在我的慢速浏览器（带有 SpiderMonkey 的 Firefox 3.0）上，用这个库进行一次这样大小的幂运算大约需要 9 秒。我正在寻找至少快 10 倍的解决方案。对于 2048 位数字来说，使用平方和乘法（通过平方求幂，http ://en.wikipedia.org/wiki/Exponentiation_by_squaring ）的明显想法太慢了：它需要多达 4096 次乘法。

升级浏览器不是一种选择。使用另一种编程语言不是一种选择。将号码发送到 Web 服务不是一种选择。

是否有更快的替代方案实施？

更新：按照下面 outis 的回答中提到的文章http://www.ccrwest.org/gordon/fast.pdf的建议，通过做一些额外的准备（即预先计算几百次幂） ，可以对 2048-位模幂运算最多仅使用 354 次模乘。（传统的平方和乘法方法要慢得多：它使用最多 4096 次模乘。）这样做在 Firefox 3.0 中将模幂运算速度提高了 6 倍，在 Google Chrome 中提高了 4 倍。我们没有得到 4096/354 的完全加速的原因是 BigInt 的模幂算法已经比平方和乘法更快，因为它使用了蒙哥马利归约 ( http://en.wikipedia.org/wiki/Montgomery_reduction ) .

更新：从 BigInt 的代码开始，似乎值得做两级手动优化（和内联）Karatsuba 乘法（http://en.wikipedia.org/wiki/Karatsuba_algorithm），然后才恢复到 base-32768 O( n^2) 在 BigInt 中实现的乘法。这将 2048 位整数的乘法速度提高了 2.25 倍。不幸的是，模运算并没有变得更快。

更新：使用http://www.lirmm.fr/arith18/papers/hasenplaugh-FastModularReduction.pdf和 Karatsuba 乘法和预计算幂（定义在http://www.ccrwest.org/gordon/ fast.pdf )，我可以在 Firefox 3.0 中将单次乘法所需的时间从 73 秒缩短到 12.3 秒。这似乎是我能做的最好的，但它仍然太慢。

更新：Flash Player 中的 ActionScript 2 (AS2) 解释器不值得使用，因为它似乎比 Firefox 3.0 中的 JavaScript 解释器慢：对于 Flash Player 9，它似乎慢 4.2 倍，对于 Flash Player 10，它似乎慢了 2.35 倍。有人知道 ActionScript2 和 ActionScript3 (AS3) 在数字处理方面的速度差异吗？

更新：Flash Player 9 中的 ActionScript 3 (AS3) 解释器不值得使用，因为它的速度与 JavaScript int Firefox 3.0 几乎相同。

更新：如果使用 Flash Player 10 中的 ActionScript 3 (AS3) 解释器int代替Number，并且Vector.<int>使用代替Array. 2048 位大整数乘法至少要快 2.41 倍。因此，可能值得在 AS3 中进行模幂运算，如果可用，在 Flash Player 10 中执行它。请注意，这仍然比 Google Chrome 的 JavaScript 解释器 V8 慢。有关各种编程语言和 JavaScript 实现的速度比较，请参阅http://ptspts.blogspot.com/2009/10/javascript-and-actionscript-performance.html 。

更新：有一个非常快速的 Java 解决方案，如果安装了 Java 插件，可以从浏览器的 JavaScript 调用。以下解决方案比使用 BigInt 的纯 JavaScript 实现快约 310 倍。

任何人都可以将此代码翻译成 Silverlight (C#) 吗？

我目前正在使用 sparc 计算机，我想知道一个数字是否是素数。

这是代码的一部分：

所以基本上我们这里有3/2。所以应该有一个1的提醒。这个提醒应该放在%Y寄存器中。但是当我查看 %Y 时，它仍然为 0。为什么 %Y 仍然为 0，而它应该提醒我 1？

我想找到 0 和 long 变量之间的质数，但我无法获得任何输出。

该程序是

谁能帮我找出程序中可能出现的错误？

我试图想出一个方法，它接受一个整数并返回一个布尔值来说明这个数字是否是素数，而且我不太了解 C；有人愿意给我一些指示吗？

基本上，我会在 C# 中这样做：

我想知道这里是否有人有他们想要分享的阿特金筛子的良好实现。

我正在尝试实现它，但无法完全理解它。这是我到目前为止所拥有的。

我几乎只是试图“翻译” Wikipedia中列出的伪代码，但它无法正常工作。所以要么我误解了什么，要么只是做错了什么。或者很可能两者都...

有一个我用作测试的前 500 个素数的列表，我的实现在第 40 号（或 41？）处失败。

索引 [40] 处的值不同
预期：179
但原为：175

您是否能够找到我的错误，您是否有可以共享的实现，或两者兼而有之？

我正在使用的确切测试如下所示：

我不知道这是否可能，但我只是想问一下。我的数学和算法技能在这里有点让我失望：P

问题是我现在有这个类可以生成达到一定限制的素数：

现在，我想要摆脱限制，以便序列永远不会停止（理论上）。

我想它可能会是这样的：

1. 从一些微不足道的限制开始
   • 找到所有质数到极限
   • 产生所有新发现的素数
   • 增加限制（通过将旧限制加倍或平方或类似的方法）
   • 转到第 2 步

最佳情况下，第二步只需要在旧限制和新限制之间工作。换句话说，它不应该一次又一次地找到最低的素数。

有没有办法做到这一点？我的主要问题是我不太了解该算法中的内容x，y例如。就像，我可以只使用相同的算法类型，但设置x为（最初y为oldLimit1）并将其运行到newLimit？或者那将如何工作？有什么聪明的头脑可以阐明这一点吗？

这样做的目的是让我不必设置这个限制。这样我就可以使用 Linq 以及Take()我需要的任意数量的素数，而不用担心限制是否足够高等等。

有没有什么好的算法可以找到最接近给定数字的素real数？我只需要在前 100 个素数左右进行搜索。

目前，我有一堆素数存储在一个数组中，我一次检查一个数字的差异（O（n）？）。