问题标签 [prime-factoring]

计算数字的最大素数的最佳方法是什么？

我认为最有效的方法如下：

1. 找到能整除的最小素数
2. 检查除法的结果是否为素数
3. 如果没有，找到下一个最低的
4. 转到 2。

我将这个假设建立在更容易计算小素数的基础上。这是对的吗？我应该研究哪些其他方法？

编辑：我现在意识到，如果有超过 2 个素数在起作用，我的方法是徒劳的，因为当结果是其他两个素数的乘积时，第 2 步失败，因此需要递归算法。

再次编辑：现在我意识到这仍然有效，因为最后找到的素数必须是最高的，因此对第 2 步的非素数结果的任何进一步测试都会导致更小的素数。

我需要找出超过 3000 亿的质因数。我有一个功能正在添加到它们的列表中......非常缓慢！它现在已经运行了大约一个小时，我认为它还有很长的路要走。我这样做是完全错误的还是预期的？

编辑：我试图找到数字 600851475143 的最大素数。

编辑：结果：

在 ML 中，我想得到一个数字的主要除数。我该怎么做，我是初学者。

似乎有几种非常快速的素数分解算法（看起来理想的一种是二次筛选）。但是，为了简单起见，我不想自己制作（可能很差）实现，而是使用现成的库。

我需要能够有效地分解最多 15 位的整数。正因为如此，我不是在寻找必须渐近最佳缩放的算法，因为我们可以假设被分解的数字小于 10 ¹⁵。

我已经查看了Wikipedia 的 Quadratic Sieve 页面上列出的一些实现。然而，一些实现似乎并没有得到很好的维护。有些没有文件；等等！我检查了一些著名的库，例如 Boost，是否有分解方法，但它们似乎没有。

谁能推荐一个符合上述标准的图书馆？

有一种简单的密码可以将数字转换为 . ( )

为了将数字（0 .. 2147483647）加密为这种表示，我（认为我）需要：

• 质因数分解
• 对于给定的p（p是 Prime ）， p 的顺序序列（即PrimeOrd(2) == 0，PrimeOrd(227) == 49）

一些例子

我的问题源代码

问题是程序 PrimeOrd 的缓慢性。你知道一些更快的解决方案来找出素数中的素数顺序吗？

标题

如果您知道如何加快查找素数的顺序，请提出一些建议。:-)

谢谢你。

PS 小于 2,147,483,648 的最大素数是2,147,483,647，它是第105,097,565 个素数。没有必要期望比 2^31 更大的数字。

KenKen 拼图是一个拉丁方格，分为边缘连接的域：单个单元格、同一行或列中的两个相邻单元格、排成一行或一列的三个单元格等。每个域都有一个标签，该标签给出了一个目标数字和单个算术运算 (+-*/)，该运算将应用于域单元格中的数字以产生目标数字。（如果域只有一个单元格，则没有给出运算符，只有一个目标 --- 为您求解正方形。如果运算符是 - 或 /，则域中只有两个单元格。）难题是（重新）构建与域的边界和标签一致的拉丁方。（我想我只见过一次具有非唯一解的谜题。）

单元格中的数字可以从 1 到拼图的宽度（高度）；通常，拼图的一侧有 4 或 6 个单元格，但可以考虑任何大小的拼图。已发布的谜题（4x4 或 6x6）中的域通常不超过 5 个单元格，但同样，这似乎不是硬性限制。（但是，如果拼图只有一个域，那么解决方案将与该维度的拉丁方格一样多......）

编写 KenKen 求解器的第一步是拥有可以在任何域中产生可能的数字组合的例程，首先忽略域的几何形状。（线性域，例如一行三个单元格，在已解决的难题中不能有重复的数字，但我们暂时忽略这一点。）我已经能够编写一个 Python 函数来处理逐个添加标签：给它拼图的宽度、域中的单元格数量和目标总和，它返回一个由有效数字加起来到目标的元组的列表。

乘法的情况让我无法理解。我可以得到一个字典，其键等于给定大小的谜题中给定大小的域中可达到的产品，其值是包含给出产品的因素的元组列表，但我无法解决一个案例- 逐案例程，甚至不是一个糟糕的例程。

将给定的乘积分解为素数似乎很容易，但是将素数列表划分为所需数量的因数让我很难过。（我冥想过 Knuth 的 TAOCP 第 4 卷的 Fascicle 3，但我还没有学会如何“理解”他的算法描述，所以我不知道他的集合分区算法是否会成为一个起点。理解 Knuth 的描述可能是另一个问题！）

我很高兴为公共域和拼图大小预先计算“乘法”字典，并将加载时间计入开销，但这种方法似乎不是一种有效的方法来处理，例如，一边拼图 100 个单元格，域大小为 2 到 50 个细胞。

我的理解是，如今许多公钥密码算法都依赖于大素数来组成密钥，而难以分解两个素数的乘积使得加密难以破解。我的理解也是，分解如此大的数字如此困难的原因之一是，所使用的数字的绝对大小意味着没有 CPU 可以有效地处理这些数字，因为我们的微型 32 位和 64 位 CPU 无法匹配对于 1024、2048 甚至 4096 位数。必须使用专门的 Big Integer 数学库来处理这些数字，而这些库本身就很慢，因为 CPU 一次只能保存（和处理）小块（如 32 位或 64 位）。

所以...

为什么你不能构建一个具有 2048 位寄存器和巨大算术电路的高度专业化的定制芯片，就像我们从 8 位到 16 位到 32 位到 64 位 CPU 一样，只是构建一个更大的芯片？该芯片不需要传统 CPU 上的大部分电路，毕竟它不需要处理虚拟内存、多线程或 I/O 等事情。它甚至不需要是支持存储指令的通用处理器。只是对巨大数字执行必要的算术计算的最低限度。

我对 IC 设计了解不多，但我确实记得学习过逻辑门的工作原理，如何构建半加器、全加器，然后将一堆加法器连接在一起进行多位运算。只是放大。很多。

现在，我相当肯定有一个很好的理由（或 17 个）以上方法行不通（否则许多比我聪明的人中的一个已经这样做了），但我很想知道为什么它行不通。

（注意：这个问题可能需要重新处理，因为我什至不确定这个问题是否有意义）

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

以下是我得到的输出：

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

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

我最近一直在阅读有关密码学中素因子的一般用途的文章。在我读到的所有地方，它都指出没有在多项式时间（而不是指数时间）中运行的“已发布”算法来查找密钥的主要因素。

如果发现或发布了确实在多项式时间内运行的算法，那么这将如何影响现实世界的计算环境，而不是理论和计算机科学的世界。考虑到我们对密码学的依赖程度会突然停止。

考虑到这一点，如果 P = NP 为真，可能会发生什么，我们在多大程度上取决于它尚未被证实的事实。

我是初学者，所以请原谅我的问题中的任何错误，但我想你会明白我的一般要点。

这是在我正在阅读的书中理解 while 循环的示例，我不太明白为什么要进行地板除法，然后是 y % x？有人可以解释这段代码，它在做什么？

谢谢！