问题标签 [primes]

我正在用 python 模拟我的加密方案，我是它的新用户。

p = 512 位数，我需要为其计算最大素数，我正在寻找两件事：

1. 处理这种大型素数分解的最快代码
2. 可以将 512 位数字作为输入并可以处理的代码。

我在其他语言中看到了不同的实现，我的整个代码都在 python 中，这是我卡住的最后一点。所以让我知道python中是否有任何实现。

请简单解释一下，因为我是 python 的新用户

抱歉英语不好。

编辑（取自以下OP的回答）：

上面的代码适用于“1238162376372637826”（有一点延迟），但将其扩展到

10902610991329142436630551158108608965062811746392 57767545600484549911304430471090261099132914243663 05511581086089650628117463925776754560048454991130443047

让蟒蛇发疯。有什么办法可以像上面一样，我可以立即计算出来吗？

我正在尝试根据用户输入生成素数。这是我到目前为止所拥有的，但我似乎无法弄清楚：

如何找到大于给定数字的最小素数？例如，给定 4，我需要 5；给定 7，我需要 11。

我想知道一些关于最佳算法的想法。我想到的一种方法是通过埃拉托色尼筛生成素数，然后在给定数之后找到素数。

我正在做 Project Euler 的第 7 题。我应该做的是计算第 10,001^个素数。（素数是一个大于 1 且只能被自身和 1 整除的整数。）

这是我目前的程序：

它可以很好地找到，比如第 100^个素数，但是使用非常大的输入（例如 10,001）运行会导致堆栈溢出。为什么，我该如何解决这个问题？

此应用程序将收到一个数字“n”。收到这个数字后，程序必须显示素数列表中的第 n 个素数。例如，如果用户输入“3”，程序应该显示“5”，因为 5 是从 2 开始的第三个素数。我知道我的代码有问题，但我不知道问题出在哪里以及我该如何解决。

给定 A，在 10^20 的数量级上，我想快速获得前几个大于 A 的素数的列表。好吧，我的需求不是那么精确 - 如果偶尔有一个合数结束也没关系在名单上。

枚举大于 A 的（可能的）素数的最快方法是什么？

有没有比遍历所有大于 A 的整数（除了明显的倍数，比如 2 和 3）并为每个整数执行素数测试更快的方法？如果不是，唯一的方法是测试每个整数，我应该使用什么素数测试？

我需要在非常大的数字之间的间隔上测试素数（在 long long 的范围内），所以我需要一些快速算法来检查一个数字是否为素数。请提出你的想法。

这篇文章说：

每个素数都可以表示为 30k±1, 30k±7, 30k±11, 或 30k±13对于某些k。这意味着我们可以使用每 30 个数字中的 8 位来存储所有素数；一百万个素数可以压缩到 33,334 字节

“这意味着我们可以使用每 30 个数字中的 8 位来存储所有素数”

这个“每 30 个数字 8 位”将用于k，对吗？但每个k值不一定只占用一位。不应该是八个 k 值吗？

“一百万个素数可以压缩到 33,334 字节”

我不确定这是怎么回事。

我们需要指出两件事：

• k的值（可以任意大）

• 来自八个州之一的州(-13,-11,-7,-1,1,7,11,13)

我没有关注“33,334 字节”是如何得出的，但我可以说一件事：随着质数的值越来越大，我们将需要更多空间来存储k的值。

那么我们如何将其修复为“33,334 字节”呢？

我想创建一个将所有素数写入文件的程序（我知道有一种流行的算法“埃拉托色尼筛法”，但我正在尝试自己制作）。我试图消除仍然具有值 1 的字节的所有复杂性，然后将它们写入文件中。

我将编写关于 RSA 的原始论文中提出的 Solovay-Strassen 素性测试。

此外，我将需要编写一个小型 bignum 库，因此在搜索 bignum 的方便表示时，我遇到了这个规范：

我还将使用 Karatsuba 方法编写一个乘法例程。

所以，对于我的问题：

在 bignum 结构中存储整数数据时使用什么基础比较方便？

注意：我不允许对 bignum 使用第三方或内置实现，例如 GMP。

谢谢你。