首页 >
整数分解
✍ dations ◷ 2025-09-02 07:20:06 #整数分解
在数学中,整数分解(英语:integer factorization)又称素因数分解(prime factorization),是将一个正整数写成几个约数的乘积。例如,给出45这个数,它可以分解成
3
2
×
5
{displaystyle 3^{2}times 5}
。根据算术基本定理,这样的分解结果应该是独一无二的。这个问题在代数学、密码学、计算复杂性理论和量子计算机等领域中有重要意义。完整的因子列表可以根据约数分解推导出,将幂从零不断增加直到等于这个数。例如,因为
45
=
{displaystyle 45=,}
3
2
×
5
{displaystyle 3^{2}times 5}
,由此可知,45可以被30 ×50,30×51,31×50,31×51,32×50,和32×51,或者 1,5,3,9,15,和 45整除。相对应的,约数分解只包括约数因子。参见约数分解算法。给出两个大约数,很容易就能将它们两个相乘。但是,给出它们的乘积,找出它们的因子就显得不是那么容易了。这就是许多现代密码系统的关键所在。如果能够找到解决整数分解问题的快速方法,几个重要的密码系统将会被攻破,包括RSA公钥算法和Blum Blum Shub(英语:Blum Blum Shub)随机数发生器。尽管快速分解是攻破这些系统的方法之一,仍然会有其它的不涉及到分解的其它方法。所以情形完全可能变成这样:整数分解问题仍然是非常困难,这些密码系统却是能够很快攻破。有的密码系统则能提供更强的保证:如果这些密码系统被快速破解(即能够以多项式时间复杂度破解),则可以利用破解这些系统的算法来快速地(以多项式时间复杂度)分解整数。换句话说,破解这样的密码系统不会比整数分解更容易。这样的密码系统包括Rabin密码系统(RSA的一个变体)以及Blum Blum Shub随机数发生器。2005年,作为公共研究一部分的有663个二进制数位之长的RSA-200已经被一种一般用途的方法所分解。如果一个大的,有n个二进制数位长度的数是两个差不多大小相等的约数的乘积,现在还没有很好的算法来以多项式时间复杂度分解它。这就意味着没有已知算法可以在O(nk)(k为常数)的时间内分解它。但是现在的算法也是比Θ(en)快的。换句话说,现在我们已知最好的算法比指数数量级时间要快,比多项式数量级时间要慢。已知最好的渐近线运行时间是普通数域筛选法(GNFS)。时间是:对于平常的计算机,GNFS是我们已知最好的对付n个二进制数位大约数的方法。不过,对于量子计算机, 彼得·秀尔在1994年发现了一种可以用多项式时间来解决这个问题的算法。如果大的量子计算机建立起来,这将对密码学有很重要的意义。这个算法在时间上只需要O(n3),空间只要O(n)就可以了。 构造出这样一个算法只需要2n量子位。2001年,第一个7量子位的量子计算机第一个运行这个算法,它分解的数是15。现在还不确切知道整数分解属于哪个复杂度类。我们知道这个问题的判定问题形式(“请问N是否有一个比M小的约数?”)是在NP与反NP之中。因为不管是答案为是或不是,我们都可以用一个素因数以及该素因数的素数证明来验证这个答案。由秀尔算法可知,这个问题在BQP中。大部分的人则怀疑这个问题不在P、NP完全、以及反NP完全这三个复杂性类别中。如果这个问题可以被证明为NP完全或反NP完全,则我们便可推得NP=反NP。这将会是个很震撼的结果,也因此大多数人猜想整数分解这个问题不在上述的复杂性类别中。也有许多人尝试去找出多项式时间的算法来解决这个问题,但是都尚未成功,因此这个问题也被多数人怀疑不在P中。有趣的是,判定一个整数是否是素数则比分解该整数简单许多。AKS算法证明前者可以在多项式时间中解决。 测试一个数是否为素数是RSA算法中非常重要的一环,因为它在一开始的时候需要找很大的素数。一个特别的因子分解算法的运行时间依赖它本身的未知因子:大小,类型等等。在不同的算法之间运行时间也是不同的。一般用途算法的运行时间仅仅依赖要分解的整数的长度。这种算法可以用来分解RSA数。大部分一般用途算法基于平方同余方法。
相关
- 叠层石叠层石(英语:Stromatolite,或称层叠石,源自希腊文strōma与lithos)可定义为“从某一点或有限的表面开始增生,并聚集石化,形成逐渐增大的沉淀物生成构造”。自然界中有许多不同型态
- 趋化性趋化性(英语:Chemotaxis,亦被称为化学趋向性)是趋向性的一种,指身体细胞、细菌及其他单细胞、多细胞生物依据环境中某些化学物质而趋向的运动(详细请看细胞迁移)。这对细菌寻找食物
- 恶性高热恶性高热、致命高热(英语:Malignant hyperthermia (MH))是病人因全身麻醉而导致的严重反应,是因为使用特定全身麻醉药而引发的罕见危及生命病症(英语:life-threatening condition),
- 种群生物系统层级关系:生物圈 > 生态系统 > 群落 > 种群 > 个体在生物学上,种群(英语:Population,或族群)指于一定空间范围内同时生活的同种生物的全部个体;或者说是有个体组成,能够而且
- 萤光显微镜荧光显微镜是一种使用荧光或磷光物质的光学显微镜,或除此之外使用反射和吸收用于研究的有机或无机物质的特性。“荧光显微镜”是指使用荧光来产生一个图像的任何显微镜,无论是
- 立克次体等立克次体(学名:Rickettsia),或者称立克次氏体,是一类细菌,但许多特征和病毒一样,如不能在培养基上培养,可以通过瓷滤器过滤,只能在动物细胞内寄生繁殖等。直径只有0.3-1μm,小于绝大
- 乱世佳人《乱世佳人》(英语:Gone with the Wind),是一部根据小说家玛格丽特·米切尔的英文同名小说《飘》(Gone with the Wind)改编的美国电影。男女主角分别由克拉克·盖博(Clark Gable)和
- 西医人体解剖学 - 人体生理学 组织学 - 胚胎学 人体寄生虫学 - 免疫学 病理学 - 病理生理学 细胞学 - 营养学 流行病学 - 药理学 - 毒理学医学是以诊断、治疗和预防生理和心理
- 未解的问题尚未解决的语言学问题(List of unsolved problems in linguistics)列举了语言学中十分关键但仍待解决的诸多问题,内容如下。以下所示问题中,既有目前已被公认无解的问题,也有已解
- 全字母句包含有字母表中所有字母并且言之成义的句子称为全字母句(英语:pangram或holoalphabetic sentence,希腊语:pan gramma(意为“每一个字母”))。全字母句被用于显示字体和测试打字机。