Re: gaussian integer modulus / Pollard's rho method on gaussian integers

[hermann@stamm-wilbrandt.de]

On 2025-11-27 11:05, Bill Allombert wrote:
> > I know there is no Gaussian Integer type in GP.
> > But could a meaningfully renamed "gimod()" function for "Gaussian 
> > integer
> > mod" be made part of GP?
>
> This requires to fix a convention for the Euclidean division for
> Gaussian integer,
> and of course not all t_COMPLEX are Gaussian integers.
OK.

> Note that GP has aleeady a function nfdiveuc to do that with a
> different interface.
Interesting — I used new gimod2() that reports divisor (like nfdiveuc, 
extended help only knows nfeltdiveuc) as well as modulus for bigger 
example:

gimod2(w,z)={
  my(u=w*conj(z),n=norml2(z));
  d=((u-gismod(u,n))/n);
  [d,w-z*d]
};

? a=190+190*I;
? b=19+4*I;
? gimod2(a,b)
[12 + 8*I, -6 - 10*I]
?

Now with nfinit I get same disvisor:

? C=nfinit(y^2+1);
? a=190+190*y;
? b=19+4*y;
? nfeltdiveuc(C,a,b)
[12, 8]~
?

But how to get the modulus from that like in gimod2?

? a-(12+8*y)*b
-32*y^2 - 10*y - 38
?


Another question, gimod() and gimod2() guarantee all operations being 
t_INT. But C looks to have some reals inside:

? C
[y^2 + 1, [0, 1], -4, 1, [Mat([1, 0.E-57 + 
1.0000000000000000000000000000000000000*I]), [1, 
1.0000000000000000000000000000000000000; 1, 
-1.0000000000000000000000000000000000000], [16, 16; 16, -16], [2, 0; 0, 
-2], [2, 0; 0, 2], [1, 0; 0, -1], [1, [0, -1; 1, 0]], [2]], [0.E-57 + 
1.0000000000000000000000000000000000000*I], [1, y], [1, 0; 0, 1], [1, 0, 
0, -1; 0, 1, 1, 0]]
?

Is nfeltdiveuc() with C guaranteed to return correct result for big 
normnl2() Gaussian integers?


Regards,

Hermann.