33

我已经有素数分解（整数），但现在我想为高斯整数实现它，但我应该怎么做呢？谢谢！

4

2 回答 2

75

事实证明这有点冗长，但我希望它能完全回答你的问题......

高斯整数是形式的复数

G = a+bi

其中i 2 = -1，并且a和b是整数。

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

这种数G的范数被定义为一个整数：norm(G) = a 2 + b 2。

可以证明范数是一个乘法性质，即：

范数(I*J) = 范数(I)*范数(J)

因此，如果您想分解一个高斯整数G，您可以利用这样一个事实， 即除G的任何高斯整数I必须满足norm(I)除norm(G)的性质，并且您知道如何找到规范（G）。

高斯整数的素数分为三类：

1 +/- i，范数为2，

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

a，其中a是3 mod 4的质数，范数为 a 2

现在把它变成一个算法......如果你想分解一个高斯整数G，你可以找到它的范数N，然后把它分解成素数。然后我们沿着这个列表工作，剥去N的素数p对应于我们原始数G的素数高斯因子q。

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

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

如果p = 3 mod 4，则q = p。但是q的范数是p 2 ，所以我们可以从norm(G)的剩余因子列表中找出另一个因子p。

p = 1 mod 4的情况是唯一一个有点棘手的情况。这相当于将p表示为两个平方和的问题：如果p = a 2 + b 2，则a+bi和a-bi形成具有范数p的高斯素数的共轭对，其中一个将是我们正在寻找的因素。

但是有了一点数论，事实证明这并不太难。考虑整数 mod p。假设我们可以找到一个整数k使得k 2 = -1 mod p。然后k 2 +1 = 0 mod p，这相当于说p将k 2 +1除以整数（因此也是高斯整数）。在高斯整数中，k 2 +1因数为 (k+i)(ki)。 p除以乘积，但不除任何一个因子。因此，p有一个非平凡的 GCD，其中每个因子(k+i)和(ki)，而 GCD 或其共轭是我们正在寻找的因素！

但是我们如何找到这样一个整数k呢？让n是介于2和p-1之间的某个整数，包括 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）整除，我们就完成了。否则，它的共轭是所需的因子。

Euclid 的高斯整数 GCD 算法几乎与普通整数相同。每次迭代都包含一个带有余数的试除法。如果我们正在寻找gcd(a,b)，

q = floor(a/b)，余数 = a - q*b，如果余数非零，我们返回gcd(b,remainder)。

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

所以分解高斯整数G的算法看起来像这样：

计算norm(G)，然后将norm(G)分解为素数p 1 , p 2 ... 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 。范数(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 2 mod p = 4。4与-1 mod 5一致。成功！ k = 2 1 = 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 8 = 1 mod 17，不好。尝试n=3代替。 3 8 = 16 模 17 = -1 模 17。成功！所以k = 3 4 = 13 mod 17。 gcd(17, 13+i) = u = 4-i , G/u = -99 -96i余数-2。不好，所以试试conjugate(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，它等于1 mod 4。再次使用 k 过程...尝试n=2, 2 26 = 52 mod 53 = -1 mod 53。然后k = 2 13 mod 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，这是我们开始的数字。

数论不甜吗？

于 2010-02-16T09:07:26.447 回答
0

如果您想要完整的单单元整数精度，请对实部和虚部使用浮点，并定义 gsub、gmul 和具有舍入系数的特殊除法 gdivr，而不是下限。这是因为 Pollard rho 分解方法需要通过 Euclid 算法的 gcd，并稍微修改 gmodulo：

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

波拉德 rho

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 编程的方法

为了安全起见，在所有计算中使用四舍五入的值，同时对整数使用浮点数。

于 2015-12-16T08:32:44.387 回答