Re: Kunerth's algorithm (determine modular square root of a number)

[hermann@stamm-wilbrandt.de]

On 2023-11-25 02:41, hermann@stamm-wilbrandt.de wrote:
> Tomorrow I will investigate why the 4 examples from Kunerth's 1878 
> paper
> do not work for now, and try to fix Kunert.gp and then post here.
>
> These are the current failures:
>
>   *** sqrt: not a prime number in Fl_sqrt [modulus]: 1124.
>   *** sqrt: not a prime number in sqrt [modulus]: 16315.
>   ***   at top-level: assert(issquare(w,&W))
>   *** Mod: impossible inverse in Fl_inv: Mod(0, 239).
>
> Kunerth's algorithm is not a general purpose modular sqrt algorithm.
> Will be interesting to see what scenarios can be processed.
Now in 4th revision you can find Kunerth.gp gist here for playing with:
https://gist.github.com/Hermann-SW/76e7cf8545c5e8b0332faeaad878e08f

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.

For computing sqrt(c) (mod b) the algorithm works with b (mod c).
If c is not a prime, PARI/GP issquare() is used instead of sqrt().
That can be slow for big c.

Sometimes a non-t_INT constant term of quadratic form e results.
In that case Kunerth.gp tries to work with -b (mod c).


Here is new example calculation:
f=-1 is forced for getting a t_INT constant term of e, by subtracting b 
in simplify() instead of adding.
Modified f value influences computation of xx:

$ m="Mod(60,5*17)" gp -q < Kunerth.gp
V=25
e=60*z^2 + 50*z + 9
f=-1
W=3
alpha=3
beta=-8
xx=[x + 4, 1; 9*x + 1, 1]
X=-4
Y=Mod(65, 85)
Y^2=Mod(60, 85)
X=-1/9
Y=Mod(20, 85)
Y^2=Mod(60, 85)
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=factor(alpha^2*x^2+(2*alpha*beta-f*b)*x+(beta^2-c));

i∈{1,2}:  X=-polcoeff(xx[i,1],0])/polcoeff(xx[i,1],1); 
Y=Mod(alpha*X+beta,b);
$
Constant term of e was square 9, 5*17-60=25 was square as well.


After "all asserts OK" output now detailed steps of Kunerth.gp are 
explained.
If you don't want that output, append " 2>/dev/null" to remove that 
stderr output.


Here is another square difference resulting in square constant of e and 
results:

$ m="Mod(13*17-7^2,13*17)" gp -q < Kunerth.gp 2>/dev/null
V=93
e=172*z^2 + 186*z + 49
f=-1
W=7
alpha=14
beta=-13
xx=[4*x - 3, 1; 49*x + 1, 1]
X=3/4
Y=Mod(108, 221)
Y^2=Mod(172, 221)
X=-1/49
Y=Mod(113, 221)
Y^2=Mod(172, 221)
all asserts OK
$


Regards,

Hermann.