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

[hermann@stamm-wilbrandt.de]

On 2025-11-14 00:22, hermann@stamm-wilbrandt.de wrote:
> ...
> from Robert Chapman and transpiled it to Pari/GP:
> https://github.com/Hermann-SW/RSA_numbers_factored/blob/main/pari/RSA_numbers_factored.gp#L142-L220
>
> Now I tried to use GP t_COMPLEX instead of a vector of two numbers for
> gaussian integers. And the code tells so much more how and what is
> done:
>
> \\ signed k (mod n) in range -floor(n/2)..ceil(n/2)
> smod(k,n)=my(m=k%n);if(2*m>n,m-n,m);
>
> \\ componentwise signed mod of gaussian integer
> gismod(a,n)=smod(real(a),n)+I*smod(imag(a),n);
>
> \\ gaussian integer w (mod z)
> gimod(w,z)={
>   my(u=w*conj(z),n=norml2(z));
>   w-z*((u-gismod(u,n))/n)
> };
> ...
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 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?

Regards,

Hermann.