Re: sqrt(x,n) for non-prime n?

[hermann@stamm-wilbrandt.de]

On 2023-11-21 15:37, Bill Allombert wrote:
> On Tue, Nov 21, 2023 at 11:56:12AM +0100, hermann@stamm-wilbrandt.de 
> wrote:
> > What can be done if modulus is not a p-adic number?
> > Like n=856 in example of:
> > https://en.m.wikipedia.org/wiki/Kunerth%27s_algorithm
>
> As I understand, this algorithm does not actually work...
> See the talk pages. This is one of the worst wikipedia page I have come 
> across
> in a long time.
>
> Cheers,
> Bill.
Which of the talk page comments says algorithm does not work?

I have Mp containing Mersenne prime exponents.
I tried issquare on gp 2.15.4 on AMD 7950X fast CPU.
While it was able to fast compute for up to p=1279, I had to stop 
computation
of issquare(Mod(-1,2^2203-3)) after 9h. So perhaps Kunerth's algorithm 
is needed
if it works ...

? foreach(Mp,p,print(p," ",issquare(Mod(-1,2^p-3))," ",gettime()))
2 1 0
3 1 0
5 1 0
7 1 0
13 0 0
17 1 0
19 0 0
31 0 0
61 1 0
89 0 0
107 0 0
127 0 4
521 0 858
607 0 0
1279 0 7630
^C  ***   at top-level: foreach(Mp,p,print(p," ",issquare(Mod(-1,2^p-3
  ***                                          ^---------------------
  *** issquare: user interrupt after 9h, 13min, 39,339 ms


Regards,

Hermann.