什么是大数分解

问题描述

精选答案

大数分解是与素性判别紧密相关的课题．对于给定的一个自然数，先对它作素性判别．若它是素数则罢，若它是合数，我们还想知道它的因子分解式．历史上及现在都有这样的数，它被判别为合数，但是没有发现它的因子(即没有分解)．例如，F8在1909年就被证明为合数，但直到1975年，才发现它的一个因子．又如，F14早在1963年就被证明为合数，但至今它的因子还不知是什么．因此，我们要系统地研究如何去分解一个已知是合数的数．下面，我们假定下面待分解的数是合数．为了方便起见，还假定，对待分解的数已经用试除法排除了它在1到10000(或105)范围内的因子．(这在计算机上是非常容易实行的事，因为1到105之间的素数和试除法都可以存储在计算机内．)

与素性判别法的产生一样，大数分解的方法的产生也是从注意合数的一些性质开始的．因而，我们要对合数的一些性质(特别是结构方面的性质)作考察和研究，由此引伸分解的方法。

其他回答

小金药师说药事

分解质因数通常用试除法，从2到trunc(n)如果有一个能整除n，则这个数就是n的一个质因数。

大数分解是一个很高深的问题，甚至跟RSA算法有很深的渊源，不是三言两语就能说清的。