IntegerMod sqrt() doesn't work for non-prime moduli

[sagetrac-dmharvey]

This one's tricky; not sure the best way to proceed. The problem is that IntegerMod's sqrt() function uses PARI for the underlying functionality, but PARI doesn't work when the modulus is not a prime, even though you would hope it still works when the modulus is a prime power.

Relevant reading is the sqrt function at

http://www.skalatan.de/pariguide/doc/Transcendental_functions.html#sqrt

e.g. some weirdness:

sage: Mod(4, 5).sqrt()
 2

sage: Mod(4, 25).sqrt()
...
<type 'exceptions.ValueError'>: self must be a square.

sage: pari(Mod(4, 25)).sqrt()
...
<class 'gen.PariError'>:  (8)

sage: pari(Mod(4, 125)).sqrt()
...
<class 'gen.PariError'>: non quadratic residue in gsqrt (51)

It would be possible I guess to cast to a pari p-adic, but that would involve testing the modulus of the ring for being a prime power on every sqrt() invocation... seems horribly inefficient.

Component: basic arithmetic

Issue created by migration from https://trac.sagemath.org/ticket/268

[williamstein]

comment:1

It works now in age-2.8.1.