高斯整数的分解有哪些好方法？

Question

高斯整数的分解有哪些好方法？

algorithmmathcomplex-numbersprime-factoringnumber-theory

35

我已经掌握了整数的质因子分解，但现在我想为高斯整数实现它，但应该如何做呢？谢谢！

- muaddib

你需要更具体地说明你想要了解什么。你使用什么平台来实现这些算法？ - Vivian River

2

平台是什么意思？ - muaddib

2

我希望我在答案中添加的细节能够指引您朝正确的方向前进。 - Jim Lewis

2个回答

0

如果您想要完整的单元格整数精度，请使用浮点数表示实部和虚部，并定义gsub、gmul和一个特殊的带有舍入系数而非向下取整的gdivr除法。这是因为Pollard rho分解方法需要通过欧几里得算法进行gcd计算，其中稍微修改了gmodulo：

gmodulo((x,y),(x',y'))=gsub((x,y),gmul((x',y'),gdivr((x,y),(x',y'))))

波拉德-洛算法

def poly((a,b),(x,y))=gmodulo(gsub(gmul((a,b),(a,b)),(1,0)),(x,y))

input (x,y),(a,b) % (x,y) is the Gaussian number to be factorized
(c,d)<-(a,b)
do 
   (a,b)=poly((a,b),(x,y))
   (c,d)=poly(poly((c,d),(x,y)),(x,y))
   (e,f)=ggcd((x,y),gsub((a,b),(c,d)))
   if (e,f)=(x,y) then return (x,y) % failure, try other (a,b)
until e^2+f^2>1
return (e,f)

一个正常的起始值是a=1，b=0。

我已经在我的博客http://forthmath.blogspot.se中使用了这种方法来编程Forth。

为了安全起见，在使用浮点数进行整数计算时，请在所有计算中使用舍入值。

- Lehs

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jim Lewis · Accepted Answer

这段话有些冗长，但我希望它完全回答了你的问题... 高斯整数是一种形如 G = a+bi 的复数，其中i² = -1，而a和b是整数。

高斯整数形成了一个唯一分解域。其中一些充当单位（例如1，-1，i和-i），一些充当质数（例如1 + i），其余的是可分解的，可以分解为质数和单位的乘积，这是唯一的，除了因子的顺序和存在一组乘积为1的单位之外。

这样一个数字G的范数定义为一个整数：norm(G) = a² + b²。

可以证明，该范数是一种乘法属性，即： norm(I*J) = norm(I)*norm(J)。

如果您想分解一个高斯整数G，您可以利用这样一个事实：任何能够整除G的高斯整数I都必须满足norm(I)整除norm(G)的属性，而您知道如何找到norm(G)的因子。

高斯整数的质数可分为三类：

1 +/- i，其范数为2，

a +/- bi，其质数范数等于1 mod 4的a^2 + b^2，

a，其中a是一个模4余3的质数，其范数为a^2。

现在将其转化为算法...如果要分解高斯整数G，您可以找到其范数N，然后将其分解为质数。然后我们按照这个列表进行操作，剥离与原始数字G的素高斯因子q相对应的N的素因子p。

只需要考虑三种情况，其中两种是微不足道的。

如果p = 2，则让q = (1+i)。（请注意，q = (1-i)同样有效，因为它们仅差一个单位因子。）

如果p = 3 mod 4，则q = p。但是q的范数是p ²，因此我们可以从剩余的norm(G)的因子列表中划掉另一个p的因子。 p = 1 mod 4情况是唯一有点棘手的情况。它等价于将p表示为两个平方数之和的问题：如果p = a ²+ b ²，那么a+bi和a-bi形成共轭对的高斯素数，其范数为p，其中一个将是我们要找的因子。

但是通过一些数论，发现这并不太困难。考虑模p的整数。假设我们可以找到一个整数k，使得k² = -1 mod p。那么k²+1 = 0 mod p，也就是说在整数中p能够整除k²+1（因此也包括高斯整数）。在高斯整数中，k²+1分解为(k+i)(k-i)。虽然p能够整除这个积，但它不能整除任何一个因子。因此，p与每个因子(k+i)和(k-i)都有一个非平凡的GCD，而这个GCD或者它的共轭就是我们要找的因子！

但我们如何找到这样一个整数k呢？让n成为介于2和p-1之间的某个整数。计算n^(p-1)/2 mod p - 这个值将是1或-1。如果是-1，则k = n^(p-1)/4，否则尝试不同的n。近一半可能的n值将给出-1 mod p的平方根，因此不需要多次猜测即可找到有效的k值。

要找到具有模p的高斯质数，只需使用欧几里得算法（稍作修改以适用于高斯整数）来计算(p, k+i)的GCD。这给出了一个试除数。如果它可以整除我们正在尝试分解的高斯整数（余数=0），那么我们就完成了。否则，它的共轭是所需的因子。

高斯整数的欧几里得GCD算法与普通整数的算法几乎完全相同。每次迭代都包括带余数的试除法。如果我们正在寻找gcd(a,b)， q = floor(a/b)，remainder = a - q*b，如果余数不为零，则返回gcd(b,remainder)。

在整数中，如果我们得到一个分数作为商，我们会向零四舍五入。在高斯整数中，如果商的实部或虚部是分数，则将其四舍五入到最近的整数。除此之外，算法是相同的。

因此，对于分解高斯整数G的算法看起来像这样：

计算norm(G)，然后将norm(G)分解成质数p₁，p₂ ... p_n。

For each remaining factor p:
   if p=2, u = (1 + i).   
      strike p from the list of remaining primes.
   else if p mod 4 = 3, q = p, and strike 2 copies of p from the list of primes.
   else find k such that k^2 = -1 mod p, then u = gcd(p, k+i)
       if G/u has remainder 0, q = u
       else q = conjugate(u)
       strike p from the list of remaining primes.
   Add q to the list of Gaussian factors.
   Replace G with G/q.
endfor

在这个过程的结尾，G是一个模为1的单位。但它不一定是1——它可以是-1、i或-i，在这种情况下，将G添加到因子列表中，使得当你将所有因子相乘以检查产品是否与原始值G匹配时，符号正确。

这是一个计算示例：在高斯整数环上，分解G = 361 - 1767i。 norm(G) = 3252610 = 2 * 5 * 17 * 19 * 19 * 53 考虑数字2，我们尝试使用q = (1+i)，并发现G/q = -703 - 1064i，余数为0。 G <= G/q = -703 - 1064i 考虑数字5，它与1 mod 4同余。我们需要找到一个好的k。尝试n=2，n^(p-1)/2 mod p = 2² mod p = 4。 4 同余于 -1 mod 5。成功！k = 2¹ = 2。 u = gcd(5, 2+i)，其结果为 2+i。 G/u = -494 - 285i，余数为0，因此我们找到了q = 2+i。 G <= G/q = -494 - 285i

考虑到17，它也与1 mod 4同余，因此我们需要找到另一个k mod 17。尝试n=2，2⁸ = 1 mod 17，不行。改为尝试n=3。3⁸ = 16 mod 17 = -1 mod 17。成功！所以k = 3⁴ = 13 mod 17。 gcd(17, 13+i) = u = 4-i，G/u = -99 -96i，余数-2。不行，尝试u的共轭=4+i。G/u = -133 - 38i，余数0。又得到一个因子！

G <= G/(4+i) = -133 - 38i

考虑到19，它与3 mod 4同余。因此我们的下一个因子是19，并从列表中删除第二个19。

G <= G/19 = -7 - 2i

考虑到53，它与4模同余。再进行k过程... 尝试n=2，2的26次方=52模53=-1模53。那么k=2的13次方模53=30。 gcd(53,30+i)=u=-7-2i。这与G相同，因此最终商G/(-7-2i)=1，无需担心-1、i或-i的因数问题。我们已找到因子(1+i)(2+i)(4+i)(19+0i)(-7-2i)。如果你把它乘起来（留给读者自己练习），你会发现积为361-1767i，这就是我们开始的数字。数论不是很棒吗？