Bill Allombert on Mon, 2 Oct 2000 21:23:49 +0200 (MET DST) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
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 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