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

[hermann@stamm-wilbrandt.de]

On 2023-11-23 13:52, hermann@stamm-wilbrandt.de wrote:
...
> Kunerth's algorithm is described here:
> https://en.wikipedia.org/wiki/Kunerth%27s_algorithm
...
> I was surprised to find a hit on amazon:
> https://www.amazon.com/Kunerths-Modular-Square-Algorithm-Explained-ebook/dp/B09K3TCQR1/ref=sr_1_1
...
> Later Bill helped me to get German language pages 327-346 from 1878 in
> this comment:
> https://math.stackexchange.com/questions/95443/how-to-compute-modular-square-roots-when-modulus-is-non-prime#comment9832085_252186
The original article was difficult to read (formula wise, not the old 
German language).

I agree with Bill that the Wikipedia page is written poorly and not 
always correct.

It seems that Paul Cheffers, the author of the 1$ ebook was the author 
of Wikipedia page as well.

While there are typos and errors in the ebook, I finally was able to 
make sense
out of what is written there, and was able to repeat the Mathematica 
computations.

So I ported the loose ebook Mathematica statements into a complete 
PARI/GP script.

Until now I just have processed 2nd ...
$ m="Mod(353,3872)" gp -q < Kunert.gp
V=94
W=6
alpha=24
beta=-15
xx=[x - 8, 1; 36*x + 1, 1]
X=8
Y=Mod(177, 3872)
Y^2=Mod(353, 3872)
all asserts OK
$

... 3rd ...
$ m="Mod(113,976)" gp -q < Kunert.gp
V=43
W=5
alpha=15
beta=-8
xx=[9*x - 49, 1; 25*x + 1, 1]
X=49/9
Y=Mod(399, 976)
Y^2=Mod(113, 976)
X=-1/25
Y=Mod(577, 976)
Y^2=Mod(113, 976)
all asserts OK
$

... and 4th ...
$ m="Mod(41,295)" gp -q < Kunert.gp
V=19
W=4
alpha=12
beta=-4
xx=[9*x - 25, 1; 16*x + 1, 1]
X=25/9
Y=Mod(226, 295)
Y^2=Mod(41, 295)
X=-1/16
Y=Mod(69, 295)
Y^2=Mod(41, 295)
all asserts OK
$

examples from the ebook.
2nd and 3rd example have 2 solutions while 1st has only 1.

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.

Regards,

Hermann.