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

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Sat, Nov 25, 2023 at 11:39:19PM +0100, hermann@stamm-wilbrandt.de wrote:
> 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.

This seems to work as follow:

Let p a prime number and N an integer, one try to find s so that s^2=p mod N.
The idea is to find a, x, y (with y coprime to N) so that 
p*y^2 = x^2 - a*N 
then obviously (x/y)^2 = p (mod N).
Apparently the trick is to note that this also implies a*N  = x^2 mod p, so
we can reduce the search by computing r = sqrt(a*N) mod p and only search
for x = ±r + z*p which leads to
p*y^2 = (±r+z*p)^2 - a*N

I suppose, the hope is that z will be easier to find than x. 

Cheers,
Bill.