The function square_root_mod_prime from sage.rings.finite_rings.integer_mod may produce an incorrect result.
Example: In [1]: mod(100, 5^7).sqrt()^2 Out[1]: 15725 In [2]: square_root_mod_prime_power(mod(100, 5^7), 5, 7)^2 Out[2]: 15725 The expected result is 100 instead of 15725. Tracing the steps I believe the error is at line 3726 of src/sage/rings/finite_rings/integer_mod.pyx Link: https://github.com/sagemath/sage/blob/1b1e6f608d1ef8ee664bb19e991efbbc68cbd51f/src/sage/rings/finite_rings/integer_mod.pyx#L3726 In this case, n = 2. I do not understand this part of the algorithm, but it appears that increasing the bound by one such that n = 3 does produce the correct answer. version(): SageMath version 7.4, Release Date: 2016-10-18 Kind regards, Mathijs van de Nes -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
