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

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

* hermann@stamm-wilbrandt.de [2025-11-27 13:15]:
[...]
> Is nfeltdiveuc() with C guaranteed to return correct result for big
> normnl2() Gaussian integers?

Yes. 

Your notation C for nfinit(y^2+1) is misleading: this has nothing to do
with complex numbers. This GP structure allows algebraic computations
in the number field Q(i) = Q[y] / (y^2+1). Whose ring of integers are
the Gaussian integers you're interested in.

It can be considered as a (tiny!) subfield of the complex numbers in two
different ways (y goes to i or -i).

This is an algebraic object. In more general context for more
complicated operations, we allow hybrid algorithms using a mix of
algebraic and floating point operations for the sake of efficiency (even
though the input and output are exact). Barring bugs, the result will
still be correct.

In this particular case, the nfelt* functions work in Q(i): no floating
point operation involved.

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/