什么是大合数的快速因子分解
发布网友
共1个回答
热心网友
数论中一个最基本、最古老而当前仍然受到人们重规的问题就是判别给定的整数是否素数(简称为素数判别或素性判别)和将大合数分解成素因子乘积(简称为大数分解)。在历史上，这个问题曾经吸引了包括费马(Fermat)、欧拉(Euler)、勒让德(Legendre)和高斯(Gauss)在内的大批数学家，他们花费了大量的时间和精力去研究这个问题。高斯在其著名的《算术探讨》(《Disquisitiones Arithmeticae》)中称道：“把素数同合数鉴别开来及将合数分解成素因子乘积被认作为算术中最重要最有用的问题之一。”我国的《易经》中也对这个问题作了研究。
素数判别和大数分解这个问题具有很大的理论价值。因为素数在数论中占有特殊的地位，鉴别它们则成为最基本的问题；而把合数分解成素因子的乘积是算术基本定理的构造性方面的需要。人类总是有兴趣问如下的问题：2131-1是否素数？由23个1组成的数是否素数？怎么分解31487694841572361？对素数判别和大数分解的研究必然会丰富人类的精神财富。更重要的是，素数判别和大数分解具有很大的应用价值。在编码中，需要讨论某类有限域及其上的多项式，这类有限域就是由素数
在快速数论变换中，要讨论Z/nZ上的卷积运算，就要知道Z/nZ的乘法群的构造，而这就依赖于将n分解成素因子的乘积。下面介绍的RSA公开密钥码*更加说明了这个问题的两个方面在实际应用中的作用。1977年，艾德利曼(Adleman)、希爱默(Shamir)和鲁梅利(Rumely)发明了一个公开密钥码*。在这个密码*中，对电文的加密过程是公开的，但是，你仅知道加密过程而未被告知解密过程则不可能对电文进行解密。他们的*就是依靠这样一个事实：我们能够很容易地将两个大素数(譬如两个百位素数)乘起来；反过来，要分解一不大整数(譬如200位)则几乎不可能。(关于RSA*的详细介绍，请参阅文献[1])。因此RSA*就与素数判别和大数分解有密切联系。首先，要具体建立一个RSA*就需要两个大素数，因而就涉及到寻找大素数的问题；而RSA*的破译之可能性就依赖于分解一个大数可能性。于是，RSA*的建立与破译就等价于素数判别与大数分解问题。近来，由于计算机科学的发展，人们对许多数学分支的理论体系重新用计算的观点来讨论。从计算的观点来讨论数论问题形成了当前很活跃的分支－—计算数论。而素数判别和大数分解成为这一分支的重要组成部分。在这一部分里提出了两个重要的、悬而未决的问题：是否存在判别素数的多项式算法？是否存在分解大整数的多项式算法？已知道“分解整数”这个问题是一个NP完全问题，因此对上面第二个问题的讨论是解决计算机科学中的难题：“NP完全问题是否一定是多项式算法可解的？”的一个突破口。因此，素数判别和大数分解对计算机科学来说也是很有价值的。
