Bill Allombert on Mon, 2 Oct 2000 21:23:49 +0200 (MET DST)

 Re: Possible bug in Mod

```>
>The following run indicates two problems in Mod.  First, when attempting
>Mod(3,9)) the program does nothing and must be interrupted with <control
>c>.  Second, sqrt(Mod(2,9)) causes the stack to double.  Note that this is
>in version 2.0.17 and may have been corrected by now.
>
>Best Regards,
>		  Jack Fearnley
>

This is not truly a bug, this is in the doc
??sqrt
sqrt(x):
...
When  the  argument  is  an integermod a non-prime  (or a

However, as Igor pointed out, this has been fixed partially by now.
You can still get false results but no infinite loop or stack doubling.
The problem is that:

1) sqrt with a non-prime modulus require factoring the modulus, and is
not implemented.

2) Checking for primality of the modulus is roughly of the same
complexity than computing the squareroot, so it is not acceptable
to check it with each square root

However if you need to compute square root modulo prime power, this is

? sqrt(2+O(3^2))
***   non quadratic residue in gsqrt
? sqrt(3+O(3^2))
***   odd exponent in gsqrt
? sqrt(4+O(3^2))
%1 = 1 + 2*3 + O(3^2)

There is now a function sqrtn for nth-root. For historical reason,
sqrtn(x,2) is faster with big exponent and slower for small one.

? sqrt(32+31^35+O(31^2000));gettime
time = 100 ms.
? sqrtn(32+31^35+O(31^2000),2);gettime
time = 30 ms.

Cheers,

Bill Allombert
```