Quadratic Residual Bug?

[Taylor Huang]

As the attachment shown. kronecker(-1,t2) returns 1, but mod(-1,t2).sqrt() says the square root cannot be done.
It seems to be a bug.

[Taylor Huang]

for copying convenience, t2=1309093727683013566817782825108625009747446954546358949698232965571021678022482795164257607242612437837777327711946435277119464351117309193681

Taylor Huang於 2020年5月7日星期四 UTC+8上午3時37分12秒寫道：

[Justin C. Walker]

> On May 6, 2020, at 12:42 , Taylor Huang <asd00012...@gmail.com> wrote:
>
> for copying convenience, t2=1309093727683013566817782825108625009747446954546358949698232965571021678022482795164257607242612437837777327711946435277119464351117309193681

This may be more feature than bug. If you break up the latter computation (below), like
t3 = mod(-1,t2) # mod(-1,x) returns x-1
t3.sqrt()

you get a response quickly, but it may not be what you are after.

t3 is 16*t4

but t4 is not prime, and is square-free (I believe Sage implicitly :-}).

Trying to factor it seems interminable (i.e., it hasn’t completed in ~5 minutes on my new iMac). It may well be beyond the software’s attention span, hence the message you got.

HTH

Justin

>
> Taylor Huang於 2020年5月7日星期四 UTC+8上午3時37分12秒寫道：
> As the attachment shown. kronecker(-1,t2) returns 1, but mod(-1,t2).sqrt() says the square root cannot be done.
> It seems to be a bug.

--
Justin C. Walker, Curmudgeon at Large
Institute for the Absorption of Federal Funds
-----------
Like the ski resort full of girls hunting for husbands
and husbands hunting for girls, the situation is not
as symmetrical as it might seem.
- Alan MacKay
--

[Dave Morris]

I don't think this is evidence of a bug, because t2 is not prime.  It is only when n is is an odd prime that kronecker(a,n) tells you whether a is a quadratic residue. See the wikipedia article on Kronecker symbol.

[Taylor Huang]

I see. But then, how should we determine quadratic residuosity in Sage? (for tractible inputs)
 

[Taylor Huang]

it seems just because t2 is composite. 

Justin C. Walker於 2020年5月7日星期四 UTC+8上午4時34分22秒寫道：

[Dave Morris]

Here is a simple function that you could use for input of reasonable size. But this discussion is no longer about sagemath development, so please ask further questions about this at ask.sagemath.org

def is_quadratic_residue(a,n):
     return(mod(a,n).sqrt() in ZZ)