algorithm - 数学：因式分解

Question

省略计算素数的方法和分解方法的细节。

为什么要分解？

它的应用有哪些？

Answer 1

哇，在这个线程中战斗如此之多。

具有讽刺意味的是，这个问题有一个主要的有效答案。

因式分解实际上在加密/解密算法中被大量使用，以至于 RSA 定期进行比赛，其中的任务是分解某些大数，这些大数是非常大的素数的倍数。

反过来，这是因为几种加密/解密算法是基于分解需要很长时间的前提，假设黑客/破解者无权访问公钥/私钥。

然后可以使用分解算法来验证任何给定的加密/解密算法的强度。

Answer 2

作为 RSA/DAS 的非对称加密基于这样一个事实，即分解是一件非常困难的事情。如果我给你一个数字，打印出来的时候有整张报纸那么大，然后告诉你“这个数字是由两个质数相乘产生的。现在请分解它”......你认为你可以吗？相信我，任何已知的方法都需要很长时间。如果不需要大量的 CPU 时间（几个世纪）或大量的内存（比世界上所有 Internet 服务器的总存储量还要多），就没有有效的方法可以做到这一点。如果您找到一种简单的方法来分解这么大的数字，例如，您会破坏电子邮件签名和 SSL (HTTPS)。

但是，还有其他与因式分解相关的任务。因式分解不仅与数字有关。有时它是关于“为什么多项式是另一个多项式的因数”。因此，数学任务可能依赖于因式分解，因此可以解决许多问题。因此，有效的因式分解具有很大的价值。甚至矩阵也可以分解。

Answer 3

它可用于破解某些类型的加密（如果它们的密钥足够小）。

对于某些类型的科学软件，您还需要它。

另一项应用是回答ProjectEuler问题。