Quelle est une bonne méthode pour factoriser les entiers gaussiens?

Cela s'est avéré être un peu verbeux, mais j'espère qu'il répond pleinement à votre question...

Un entier de Gauss est un nombre complexe de la forme

G = a+bi

Où je² = -1, et un et b sont des nombres entiers.

Les entiers gaussiens forment un domaine de factorisation unique. Certains d'entre eux agissent comme des unités (p. ex. 1, -1, j', et -i), certains comme les nombres premiers (par exemple, 1 + i), et le reste composite, qui peut être décomposé comme un produit de nombres premiers et d'unités qui est unique, mis à part l'ordre des facteurs et la présence d'un ensemble d'unités dont le produit est 1.

Le norme d'un tel nombre G est défini comme un nombre entier: norme(G) = a² + b² .

On peut montrer que la norme est une propriété multiplicative, c'est-à-dire:

Norme(I*J) = norm(I)*norme(J)

Donc, si vous voulez factoriser un gaussien integer G, vous pouvez profiter du fait que tout entier de Gauss , je, ce qui divise G doit satisfaire à la propriété norme(I) divise norme(G), et vous savez comment trouver les facteurs de norme(G).

Les nombres premiers des entiers gaussiens se divisent en trois catégories:

1 +/- j' , avec la norme 2,

A +/- bi, avec le premier norm un²+b² conforme à 1 mod 4 ,

Un, où un est un nombre premier congru à 3 mod 4 , la norme un²

---

Maintenant, pour transformer cela en un algorithme...si vous voulez factoriser un entier gaussien G , vous pouvez trouver sa norme N, puis la factoriser en entiers premiers. Puis nous travaillons notre chemin vers le bas de cette liste, épluchant les facteurs premiers p de N qui correspondent pour amorcer les facteurs gaussiens q de notre nombre original G.

Il n'y a que trois cas à considérer, et deux d'entre eux sont triviaux.

Si p = 2, laissez - q = (1+i). (Notez que q = (1-i) fonctionnerait aussi bien, car ils ne diffèrent que par un facteur unitaire.)

Si p = 3 mod 4, q = p. Mais la norme de q est p², afin que nous puissions grève un autre facteur de p à partir de la liste des autres facteurs de norme(G).

Le P = 1 mod 4 cas est le seul qui est un peu délicat à traiter. Il est équivalent au problème d'exprimer p comme somme de deux carrés: if p = a² + b², alors a+bi et a-bi former un conjugué paire de Gauss nombres premiers avec norm p, et l'un d'eux sera le facteur que nous recherchons.

Mais avec un peu de théorie des nombres, il s'avère que ce n'est pas trop difficile. Considérons les entiers mod P. supposons que nous puissions trouver un entier k tels que k² = -1 mod p. Alors k²+1 = 0 mod p, ce qui est équivalent à dire que p divise k²+1 dans les entiers (et donc aussi le Entiers de gauss). Dans les entiers gaussiens, k²+1 facteurs dans (k+i)(k-i). p divise le produit, mais ne divise pas, soit facteur. Par conséquent, p a un GCD non trivial avec chacun des facteur (k+i) et (k-i), et que PGCD ou de son conjugué est l' facteur que nous recherchons!

, Mais comment pouvons-nous trouver un tel entier k? Soit N un entier entre 2 et p-1 inclus. Calculer n^(p-1)/2 mod p -- cette valeur sera soit 1 ou -1. Si -1, alors k = n^(p-1)/4, sinon, essayez un autre n. Près de la moitié des valeurs possibles de N donnez-nous une racine carrée de -1 mod p, donc il ne prendra pas beaucoup d'essais pour trouver une valeur de k, ce qui travail.

Pour trouver les nombres premiers gaussiens avec norm p , utilisez simplement l'algorithme D'Euclide (légèrement modifié pour fonctionner avec des entiers gaussiens) pour calculer le GCD de (p, k+i). Cela donne un diviseur de procès. Si elle divise uniformément le Entier gaussien nous essayons de factoriser (reste = 0), nous avons terminé. Sinon, son conjugué est le désiré facteur.

L'algorithme GCD D'Euclide pour les entiers gaussiens est presque identique à cela pour les entiers normaux. Chaque itération comprend une section de première instance avec le reste. Si nous recherchons gcd (a, b),

Q = plancher (a / b), reste = a-q * b , et si le reste est non nul nous retournons gcd (B, reste) .

Dans les entiers, si nous obtenons une fraction comme quotient, nous l'arrondissons vers zéro.
Dans les entiers gaussiens, si le réel ou les parties imaginaires du quotient sont des fractions, elles sont arrondies à l'entier le plus proche. En outre, l' les algorithmes sont identiques.

Ainsi, l'algorithme pour factoriser un entier gaussien G ressemble à quelque chose comme ce:

Calculer norme(G), alors le facteur de norme(G) en nombres premiers 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

À la fin de cette procédure, G est une unité de la norme 1. Mais ce n'est pas nécessairement 1 -- il pourrait être -1, j', ou -i, dans ce cas, ajoutez G à la liste des facteurs, pour que les signes sortent juste quand vous multipliez tous les facteurs pour voir si le produit correspond à la valeur d'origine de G .

---

Voici un exemple travaillé: factor G = 361-1767i sur les entiers gaussiens. norme(G) = 3252610 = 2 * 5 * 17 * 19 * 19 * 53

Considérant 2, nous essayons q = (1+i), et de trouver G/q = -703 - 1064i avec le reste 0.

G

Considérant 5, nous voyons qu'il est conforme à 1 mod 4. Nous devons trouver un bon k . En essayant n=2, n^(p-1)/2 mod p = 2² mod p = 4. 4 correspond à -1 mod 5. Succès! k = 2¹ = 2. u = pgcd(5, 2+i), qui travaille à être 2+i. G/u = -494 - 285i, avec le reste 0, si nous trouvons q = 2+i.

G

Considérant 17, il est également conforme à 1 mod 4, de sorte que nous devons trouver une autre K mod 17 . En essayant n=2, 2⁸ = 1 mod 17, rien de bon. Essayez N = 3 à la place. 3⁸ = 16 mod 17 = -1 mod 17. Succès! Donc k = 3⁴ = 13 mod 17. pgcd(17, 13+i) = u = 4-je, G/u = -99-96 i avec le reste -2. Pas bon, donc, essayez conjugué(u) = 4+i. G / u = -133-38i avec le reste 0. Un autre facteur!

G

Considérant 19, il est conforme à 3 mod 4. Donc notre prochain facteur est 19, et nous frappons la deuxième copie de 19 de la liste.

G

Considérant 53, il est conforme à 1 mod 4 . Encore une fois avec le processus K... En essayant n=2, 2²⁶ = 52 mod 53 = -1 mod 53. Alors k = 2¹³ mod 53 = 30. pgcd(53,30+i) = u = -7 - 2i. C'est identique à G , donc la finale quotient G/(-7-2i) = 1, et il n'y a pas de facteurs de -1, j', ou -i inquiéter Au sujet.

, Nous avons trouvé facteurs (1+i)(2+i)(4+i)(19+0i)(-7-2i). Et si vous multipliez que (à gauche comme un exercice pour le lecteur...), et voilà, la le produit est 361-1767i , qui est le nombre avec lequel nous avons commencé.

La théorie des nombres n'est-elle pas douce?