分析高斯整数的好方法是什么？

Question

我已经有了素数因子化(对于整数),但现在我想用高斯整数来实现它,但我该怎么做呢？谢谢!

Answer 1

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

甲高斯整数的形式为一个复数

G = a + bi

其中i ² = -1,a和b是整数.

高斯整数形成唯一的分解域.其中一些作为单位(例如1,-1,i和-i),一些作为素数(例如1 + i),其余作为素数,可以作为素数和单位的乘积分解,除了因素的顺序和一组产品为1的单位的存在.

将这样的数G的范数定义为整数:范数(G)= a ² + b ².

可以证明,规范是乘法性质,即:

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

因此,如果你想要一个高斯整数G因子,你可以利用这样一个事实, 即除以G的任何高斯整数I必须满足norm(I)除以norm(G)的属性,并且你知道如何找到因子规范(G).

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

1 +/- i,标准2,

a +/- bi,其素数为² + b ^2,与1 mod 4相同,

a,其中a是3 mod 4的素数,其范数为²

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

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

如果p = 2,则令q =(1 + i).(注意q =(1-i)同样可以正常工作,因为它们只是单位因子不同.)

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

在P = 1个模4的情况下是唯一的一个,这是一个小技巧来处理.这相当于将p 表示为两个平方之和的问题:如果p = a ² + b ²,则a + bi和a-bi形成具有范数p的高斯素数的共轭对,其中一个将是我们正在寻找的因素.

但是根据一些数论,事实并非如此困难.考虑整数mod p.假设我们可以找到一个整数k,使得k ² = -1 mod p.然后k ² +1 = 0 mod p,这相当于说p在整数中除以k ² +1(因此也就是高斯整数).在高斯整数中,k ² +1因子变为 (k + i)(ki). p除了产品,但不分割任何一个因素.因此,p具有与每个因子(k + i)和(ki)的非平凡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),我们就完成了.否则,其共轭是期望的因素.

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

q = floor(a/b),余数= a - q*b,如果余数非零,则返回gcd(b,余数).

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

因此,分解高斯整数G的算法看起来像这样:

计算范数(G),然后将因子范数(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超过高斯整数. 范数(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模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-389

考虑到19,它与3 mod 4一致.所以我们的下一个因素是19,我们从列表中击出19的第二个副本.

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

考虑到53,它与1 mod 4一致.再次与k个进程...试图n = 2时,2 ²⁶ = 52模53 = -1模53.然后k = 2 ¹³ 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,这是我们开始的数字.

数论不甜吗？