Re: Possible bug in Mod

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

>      
>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
non-prime-adic), the result is undefined. 

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
implemented, just use p-adic numbers.

? 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