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

[Karim Belabas <Karim.Belabas@u-bordeaux.fr>]

* Bill Allombert [2025-11-27 11:06]:
> On Thu, Nov 27, 2025 at 08:52:44AM +0100, hermann@stamm-wilbrandt.de wrote:
> > I looked at this again, and realized what is going on.
> > The code does the same [w/z = w*conj(z)/norml2(z)] as
> > 
> > qr = w/z
> > gi = round(real(qr)) + I*round(imag(qr)));
> > r = w - gi*z
> > 
> > but completely keeping everything a t_INT during computation
> > since (u-gismod(u,n)) is guaranteed to be a multiple of n.

I advise the simpler (and I believe more efficient):

  gimod(w, z) = my(q = round(w / z)); [q, w - q*z];

(this makes sense in Q(i), not only Z[i])

> > I tried to use "\" for that reason, but GP errors with
> > "_\_: forbidden division t_COMPLEX \ t_INT."
> > 
> > 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?
[...]
> Note that GP has already a function nfdiveuc to do that with a
> different interface.

Rather nfeltdivrem (return [q,r]) and nfeltdiveuc (return q).

For Gaussian or Eisenstein integers these function return the expected
Euclidean quotient and remainders (for some arbitrary normalization,
which happens to be the same as the above gimod).

For general elements (not assumed integral) in general number fields
(not assumed Euclidean), they return a pair [q,r] such that a - q*b = r
is "small".

There are generic alternatives: I don't think we need that function in GP.

Cheers,

    K.B.
-- 
Pr. Karim Belabas, U. Bordeaux, Vice-président en charge du Numérique
Institut de Mathématiques de Bordeaux UMR 5251 - (+33) 05 40 00 29 77
http://www.math.u-bordeaux.fr/~kbelabas/