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

[hermann@stamm-wilbrandt.de]

I used gaussian integer modulo since years, eg. for determining sum of 
two squares for a prime =1 (mod 4) [before I learned about 
"gcd(lift(sqrt(Mod(-1,p)))+I,p)"]. I started with 2010 Python code 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 use it for Pollard's rho factorization on gaussian integers, given one 
sum of two squares representation:

? sq2=19+4*I;
? a=19+19*I;
? a=gimod(a^2,sq2)
%12 = -8 + 6*I
? a=gimod(a^2,sq2)
%13 = 8 - I
? gcd(norml2(a),norml2(sq2))
%14 = 13
?


Pollard-Rho on complex numbers can be nicely viewed with block 
characters GP "graphics":

$ v="[12,1]" w="[10,2]" n=10 gp -q < t.gp
1 [-2, 1] [3, -4] [-5, 5] 5
2 [-2, 1] [3, 1] [-5, 0] 5
3 [3, 1] [-4, 5] [7, -4] 5
4 [3, 1] [0, -3] [3, 4] 5
5 [0, -3] [3, 1] [-3, -4] 5
6 [0, -3] [-4, 5] [4, -8] 5
7 [-4, 5] [0, -3] [-4, 8] 5
8 [-4, 5] [3, 1] [-7, 4] 5
9 [3, 1] [-4, 5] [7, -4] 5
10 [3, 1] [0, -3] [3, 4] 5
░░  ░░  ░░  ░░  ░░  ░░  ██  ██  ██  ██  ██  ██  ░░  ░░  ░░  ░░  ░░  ░░  
░░

██  ██  I   ██  ██  ██  ██  ██  ██  ██  ██  ██  ░░  ░░  ░░  ░░  ░░  ░░  
░░

██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ░░  ░░  ░░  ░░  ░░  ░░  
░░

██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ░░  ░░  ░░  ░░  ░░  ░░  
░░

██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ░░  ░░  ░░  ░░  @   ░░  
░░

██  ██  ██  ██  ██  ██  ██  ██  ██  H   ██  ██  ░░  ░░  ░░  ░░  ░░  ░░  
██

██  ██  ██  ██  ██  ██      ██  ██  ██  ██  ██  ██  ░░  ░░  ░░  ░░  ░░  
░░

░░  ██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ░░  ░░  ░░  ░░  ░░  
░░

░░  ██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ░░  ░░  ░░  ░░  ░░  
░░

░░  ██  ██  ██  ██  ██  J   ██  ██  ██  ██  ██  ██  ░░  ░░  ░░  ░░  ░░  
░░

░░  ██  ██  ██  ██  ██  ██  ██  ██  A   ██  ██  ██  ░░  ░░  ░░  ░░  ░░  
░░

░░  ██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ██  ░░  ░░  ░░  ░░  ░░  
░░

░░  ██  ██  ██  ██  ██  ██  ░░  ░░  ░░  ░░  ░░  ░░  ░░  ░░  ░░  ░░  ░░  
░░

-6,-6
$


Regards,

Hermann.