普通数域筛选法

易经学习

天地变化的道理

分类目录

使用率很高网站

文章列表

生活要常常分享

维基百科

您身边百科全书

产品秀秀

免费为您秀产品

普通数域筛选法

点击查看词条快照

在数论中，普通数域筛选法（GNFS）是已知效率最高的分解整数的算法。分解整数"n"（由个位元组成）需要 formula_1 步（参见L符号）。它是从引申出来的。如果条件"数域筛"没有限定条件，就是指普通数域筛选。方法. 我们选择两个不可约分的最高次项为d和e的两个多项式"f(x)"和"g(x)"，令通根m是f和g mod n的根；则他们会是"m"阶，同时次项"d" 和 "e"比较低。选择最高次项为d和e的两个多项式f（x）和g（x），它们具有整数系数，在有理数上不可约，并且在mod n时具有共同的整数根m。选择这些多项式的最佳策略尚不明确。一种简单的方法是为多项式选择一个次数d，考虑n^(1/d)的多个不同m（允许在-m和m之间的数字），并选择f（x）作为系数最小d 且 g（x）为 x − m的多项式。考虑数字环Z [r1]和Z [r2]，其中r1和r2是多项式f和g的根。由于f为d次且具有整数系数，因此如果a和b为整数，则(b^d)·f（a / b）也将为r，我们将其称为r。类似地，s ＝ (b^e)·g（a / b）是整数。目的是找到a和b的整数值，这些整数值同时使r和s相对于所选质数的底数平滑。如果a和b小，则r和s也将小，大约为m的大小，并且我们有更好的机会使它们同时平滑。具有足够多的数对(r,s)，使用高斯消去法，可以同时使某些r和相应s的乘积成为平方。需要一个稍微强一些的条件-它们是数字中的平方范数，但是该条件也可以通过此方法来实现。每个r都是a-r1b的范数，因此相应因子a-r1b的乘积是Z [r1]中的平方，类似地，因子a-r2b的乘积是Z [r2]中的平方，并且也可以计算出“平方根”。应该指出的是，使用高斯消去法不能给出算法的最佳运行时间。取而代之的是使用稀疏矩阵求解算法，例如Block Lanczos或Block Wiedemann。由于m是f和g mod n的根，因此从环Z [r1]和Z [r2]到环Z / nZ（整数mod n）存在同态，它们将r1和r2映射到m，并且这些同态将把每个“平方根”（通常不表示为有理数）映射为其整数表示。现在，可以通过两种方式将因子a-mb mod n的乘积作为一个平方来获得-每个同态一种。因此，可以找到两个数字x和y，其中x^2- y^2被n整除，并且又有可能至少有一半通过找到n和x-y的最大公约数而得到。

财务管理

实变函数论

品质管理

能级相关图

王芗斋

胸腺

关塔那摩湾

尤彭熙

滚石唱片

图波列夫Tu-144

库乐队

六合八法拳