Kunerth's algorithm from 1878, for determining modular sqrt

Kunerth.gp

assert(b,s)=if(!(b), error(Str(s)));

m=eval(getenv("m"));
b=m.mod;
c=lift(m);

if(ispseudoprime(c),s=sqrt(Mod(-b,c)),issquare(Mod(b,-c),&s));
V=r=lift(s);;
print("V=",r);

e=simplify(((c*z+r)^2+b)/c);
f=1;
w=polcoeff(e,0);
if(type(w)!="t_INT"||w<0,e=simplify(((c*z+r)^2-b)/c);f=-1;w=polcoeff(e,0));
print("e=",e);
print("f=",f);
assert(issquare(w,&W));
print("W=",W);

beta=-(V\W);
alpha=W*(V+W*beta);
print("alpha=",alpha);
print("beta=",beta);

xx=alpha^2*x^2+(2*alpha*beta-f*b)*x+(beta^2-c);
print("xx=",xx);
nfr=nfroots(,xx);
print("nfr=",nfr);

{
  foreach(nfr,X,
    Y=Mod(alpha*X+beta,b);
    if(lift(Y^2)==c,
      print("X=",X);
      print("Y=",Y);
      print("Y^2=",Y^2)));
}

print("all asserts OK");

write("/dev/stderr", "\nb=m.mod; c=lift(m); V=r=lift(\"sqrt\"(Mod(-b,c)));");
write("/dev/stderr", "e=simplify(((c*z+r)^2±b)/c); f=±1; W=sqrt(polcoeff(e,0));");
write("/dev/stderr", "beta=-(V\\W); alpha=W*(V+W*beta);");
write("/dev/stderr", "xx=alpha^2*x^2+(2*alpha*beta-f*b)*x+(beta^2-c);  nfr=nfroots(,xx);");
write("/dev/stderr", "\n∀X∈nfr: Y=Mod(alpha*X+beta,b);");

@Hermann-SW : for example, it fails with

issquare(Mod(-0xdc4e445b69fe9483216d0fa85492b4656287bfb2fb4da5b65f0b86cc2c073f3ee24a038d3d0e88c78b722b466c5ca1c89792c368ed182a5a13df919cac7fe335173cd04f23769d5ef027290f34a86e8fcab014f1a19d395b0662c5c52424a38796dd6f2394047d716abb6f48cc46abee6e2be3168348b456d5878cbec0b57d0f,0x400000000000984000000000a47f300000006ab7d5a000002e4d6f2424000e2917a6d7fc032239b4e7549381c35bcbc34cfb4e521c8ede355b00b84539f4c2b46ddf62bea6213647b859d007dc06484f3feee03b4a2bdc61a0d44186ac9a02197ddfcc49),&s)

and even then shouldn’t it be :

issquare(Mod(-b,c),&s)

instead of :

issquare(Mod(b,-c),&s)

@Hermann-SW also

xx=alpha^2*x^2+(2*alpha*beta-f*b)*x+(beta^2-c)

Doesn’t seems to work for the rare cases where beta=0 like the cases depicted in the book.

Hi,
I didcussed this on PARI/GP mailing list last year.
This posting names a big restriction of my implementation:
https://pari.math.u-bordeaux.fr/archives/pari-users-2311/msg00061.html

    It only works if constant term of quadratic form is a square.
    The Kunerth paper examples show how to deal with non-square constant term.
    But that is complex and not part of Kunerth.gp yet.

I cannot find the other posting on that mailing list where someone seriously said that Kunerth algorithm cannot work in general.

I will come back to this after having become student of Mathematics this October (at age of 60) — too much other stuff to investigate right now (CPUs benchmark for M_52 PRP, play with different GPUs to become even faster than CPUs, determining M_52=x¹+3*y², RSA_numbers_factored, 100 USD price money factoring challenge I started, ...).

@Hermann-SW ok for seeing later why some of the example of the ebook don’t work with your code.

1 last short question anyway I need the response soon : when your code in nfroots returns 2 valid square it just returns $Y$ and $−Y$. When the modulus is composite, there’s at least 2 more numbers. Is it possible to tweak the algorithm so that it return a different possible square root than with your code ?

Thanks for recovery this nice algorithm which is quite forgotten these days.

I've tried

$ m="Mod(861,1189)" gp -q < Kunerth.gp 
V=0
e=861*z^2 - 29/21
f=-1
  ***   at top-level: assert(issquare(w,&W))
  ***                 ^----------------------
  ***   in function assert: if(!(b),error(Str(s)))
  ***                               ^--------------
  ***   user error: 0
W=W
alpha=0
beta=0
xx=1189*x - 861
  ***   at top-level: nfr=nfroots(,xx)
  ***                     ^------------
  *** nfroots: incorrect type in nfrootsQ [not in Z[X]] (t_POL).
nfr=nfr
  ***   at top-level: foreach(nfr,X,Y=Mod(alpha*X+beta,b);if(lift(Y^
  ***                 ^----------------------------------------------
  *** foreach: incorrect type in foreach (t_POL).
all asserts OK

b=m.mod; c=lift(m); V=r=lift("sqrt"(Mod(-b,c)));
e=simplify(((c*z+r)^2±b)/c); f=±1; W=sqrt(polcoeff(e,0));
beta=-(V\W); alpha=W*(V+W*beta);
xx=alpha^2*x^2+(2*alpha*beta-f*b)*x+(beta^2-c);  nfr=nfroots(,xx);

∀X∈nfr: Y=Mod(alpha*X+beta,b);

and 123^2 = 861 (mod 1189)