Re: How to factor integer over Z[i]?

[Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr>]

* Andrew Lelechenko [2012-08-06 16:40]:
> I can factor an integer over the ring of integers and I can factor a
> Gaussian integer over the ring of Gaussian integers:
> 
> ? factor(25)
> %5 =
> [5 2]
> ? factor(5+I)
> time = 0 ms.
> %2 =
> [     -I 1]
> [  1 + I 1]
> [2 + 3*I 1]
> 
> But how should I ask PARI/GP to factor an integer over Gaussian
> integers? I tried for example factor(5+0*I), but it doesn't work well.

Here's a simple possibility:

\\ assume n is a t_INT
Zi_Z_factor(n) = my (f = factor(n*I)); f[1,1] /= I; f;

(17:02) gp > Zi_Z_factor(5)
%1 = 
[1 - 2*I 1]

[1 + 2*I 1]

This is not a very flexible hack. You can factor elements over arbitrary
(principal) number fields as follows:

  ? K = bnfinit(y^2 + 1)   \\ here, Q(i) ~ Q[y]/(y^2+1)
  ? F = idealfactor(K, 5);
  ? F[,1] = apply(x->nfbasistoalg(K,bnfisprincipal(K,x)[2]), F[,1]);
  ? F
  %4 = 
  [ Mod(y - 2, y^2 + 1) 1]

  [Mod(-y - 2, y^2 + 1) 1]

(Some version of this will also work over non-principal fields, but you
have to test all possible products of the prime ideal factors for
principal ideals, and you no longer have uniqueness, of course.)

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux1.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP]
`