square_root_mod_prime runs indefinitely

284 views

Skip to first unread message

Dikson

unread,

Sep 4, 2021, 1:30:08 PM9/4/21

to sage-support

square_root_mod_prime seems to run without eventually finishing in some cases.

tried on my local machine and on https://sagecell.sagemath.org/.

to reproduce:

from sage.rings.finite_rings.integer_mod import square_root_mod_prime

square_root_mod_prime(mod(12, 17)) # this doesn't finish

seems like it runs ok when there is a square root. but according to the documentation, it should also finish even when there's no answer, but with a wrong solution.

sage.rings.finite_rings.integer_mod.square_root_mod_prime(a, p=None)¶Calculates the square root of a, where a is an integer mod p; if a is not a perfect square, this returns an (incorrect) answer without checking.

can someone confirm that this is really a bug or am I doing something wrong?

Emmanuel Charpentier

unread,

Sep 12, 2021, 5:37:42 AM9/12/21

to sage-support

I find the same thing.

BTW, there is no square root of 12 modulo 17 :

sage: R1.<t>=Zmod(17)[]
sage: %time (t^2-12).roots()
CPU times: user 396 µs, sys: 2 µs, total: 398 µs
Wall time: 407 µs
[]

Direct computation seems faster in this case, either in Zmod(17)

sage: %time [t for t in Zmod(17) if t^2==R1(12)]
CPU times: user 188 µs, sys: 0 ns, total: 188 µs
Wall time: 194 µs
[]

and even faster in SR :

sage: %time [u for u in range(17) if (u^2)%17==12]
CPU times: user 87 µs, sys: 0 ns, total: 87 µs
Wall time: 93.5 µs
[]