问题标签 [factorization]

因此，对于我的任务，我必须编写一个程序，要求用户输入整数，然后打印出该数字的素数分解。这就是我所拥有的：

我现在遇到的问题是，每当我使用数字 15453 运行它时，我都会得到一个从 1 到 100 的每个因子及其指数的列表，当我只想要主要因子时，我不知道如何继续。

我的任务是使用费马分解方法分解非常大的合数。这些数字是 1024 位大，大约是 309 个十进制数字。

我想出了下面的 Python 代码，它使用该gmpy2模块来确保准确性。它只是Wikipedia 页面上显示的伪代码的 Python 实现。我阅读了该页面上的“筛选改进”部分，但不确定如何实施。

此代码对于小数字运行得相当快，但对于与问题中给出的数字一样大的数字则需要很长时间。如何提高此代码的速度？我不是在寻找为我编写代码的人，但希望能得到一些建议。感谢您的任何回复。

我只是计算机科学的初学者。我学到了一些关于运行时间的知识，但我不能确定我的理解是正确的。所以请帮助我。

所以整数分解目前不是多项式时间问题，而是素性检验。假设要检查的数字是n。如果我们运行一个程序只是为了确定从 1 到 sqrt(n) 的每个数字是否可以整除 n，如果答案是肯定的，则存储该数字。我认为这个程序是多项式时间，不是吗？

我错的一种可能方法是分解程序应该找到所有素数，而不是发现的第一个素数。所以也许这就是原因。

然而，在公钥密码学中，找到一个大数的素因数对于攻击密码学至关重要。由于通常一个大数（公钥）只是两个素数的乘积，所以找到一个素数就意味着找到另一个素数。这应该是多项式时间。那么为什么攻击很难或不可能呢？

通常我会进行素数分解并获得所有素数，然后我会进行排列和组合以找到所有因数。

例如：1824 是我要考虑的数字。现在我需要 300 中的 1824 的无因数。

有什么诀窍吗？？

我有这个问题需要解决Xin AX=B. A的数量级为 15000 x 15000，并且是稀疏且对称的。B是 15000 X 7500 并且不是稀疏的。求解 X 的最快方法是什么？

我可以想到2种方法。

1. 最简单的方法，X = A\B

2. 使用 for 循环，

   /li>

有没有比上述两种更好的方法？如果不是，我提到的两者之间哪一个最好？

我正在为 R 中的 NMF（非负矩阵分解）寻找一个包/如果可能的相对现成的解决方案，它可以处理缺失值（NA）而不将它们视为 0。

对于一个简单的推荐系统，目标实际上是通过分解的乘积来估计这些缺失值。

NMF CRAN 包很棒，但似乎无法做到这一点（它最近在 CRAN 之外的延续也不能），而且我找不到合适的替代包......

我尝试使用pymfmodule对我的数据集应用矩阵分解。如pymf网站上的示例所述，我使用non-negative matrix factorization，所以我得到了一些W- 和 -H矩阵。我如何确保W返回的 -vectors 是按解释的方差排序的？我在手册中找不到它，在我的所有测试中都是如此。如果已经完成，我想避免再次对它们进行排序。

如果不是：有没有一般最快的方法？

我想到了类似的东西

或者

?

我已经为家庭作业设置了这个问题：

费马在 1643 年使用了另一种因式分解方法。它更适合寻找大因数而不是小因数。假设 n 是一个奇数，并且 n = u × v。由此得出 n = x^2 − y^2 ，其中 x = (u + v)/2 和 y = (v − u)/2 都是整数数字（为什么？）。费马方法包括系统地搜索 x 的最小值，其中存在 x ^2 - y^2 = n 且 0 ≤ y < x 的 y。

练习 11. x 的最小可能值是多少，也就是说，我们应该从这个值开始搜索？假设在某个阶段，搜索范围缩小到 x ≥ p 和 y ≥ q。设 r = p^2 - q^2 - n。如果 r = 0，那么我们就完成了。如果 r < 0，我们应该如何改变 p 或 q？我们如何改变 r 以保持 r = p^2 - q^2 - n？如果 r > 0 怎么办？为什么这种方法保证对所有奇数 n 终止？设计一个函数 search 以便 search pqr 执行搜索。因此设计一个函数 fermat 用于返回给定奇数的两个因子。

这是我到目前为止所拥有的：

这适用于某些数字，例如 33（我得到 (3,11) 的预期），但不适用于其他数字，例如 99（我得到 (1,99) 而不是 (9,11)）。我想我需要对 q 的初始值使用不同的东西。一些提示将不胜感激。

我尝试将 q 的初始值更改为isqrt( abs(p*p-n))，但这仍然使 99 为 (3, 33) ，这是不正确的。

我已经设法使 Eulers Totient Function 的一个版本工作，尽管它适用于较小的数字（与我需要计算的 1024 位数字相比，这里较小）

我的版本在这里-

虽然这适用于较小的数字，但它通过迭代从 1 到正在计算的数字的所有可能来工作。对于大的 BigInteger，这是完全不可行的。

我已经读过可以在每次迭代中划分数字，从而无需逐个遍历它们。我只是不确定我应该除以什么（我看过的一些示例是用 C 语言并使用 long 和平方根 - 据我所知，我无法计算出准确的BigInteger 的平方根。我还想知道，如果对于像这样的模运算，函数是否需要包含一个参数来说明 mod 是什么。我完全不确定，所以任何建议都非常感谢。

谁能在这里指出我正确的方向？

PS 当我发现修改 Euler Totient Function时，我删除了这个问题。我对其进行了调整以与 BigIntegers 一起使用-

它确实给出了准确的结果，当传递一个 1024 位数时它会永远运行（我仍然不确定它是否完成，它已经运行了 20 分钟）。

我必须使用 MKL 来求解线性方程组。该方程组用于求解 2D 泊松问题，因此正好有 5 条对角线与 0 不同。系统 Ax=b 的矩阵 A 是方阵，其大小为 n*n。我检查了英特尔的文档，我对调用顺序有点困惑。原型是：

1）matrix_order。Afaik矩阵的顺序是行数和列数之间的最大值。图书馆不应该从第二个和第三个参数中找出它吗？

2)m 和 n。这些是指原始矩阵 A 还是带存储中的表示？

3）带存储。鉴于问题的结构，我在主对角线上方有 d 条对角线，在主对角线下方有 d 条对角线，因此，包括分解的额外行，带存储的内存区域应该有 (n*n)*(3*d+ 1）元素。元素是按列的。我对吗？

4）领先的维度。这应该是 (3*d+1)

任何帮助表示赞赏