libnum
libnum copied to clipboard
Modular square root by power of 2
Function sqrtmod_prime_power appears to fail when the modular is a power of 2 instead of a power of an odd prime:
>>> list(libnum.sqrtmod_prime_power(3, 2, 3))
[7, 5, 1, 3]
>>> list(libnum.sqrtmod_prime_power(1, 2, 3))
[1, 3, 5, 7]
Here it erroneously found the same solutions for the equations x**2 == 3 (mod 8) and x**2 == 1 (mod 8).
The same wrong result is returned with sqrtmod as well:
>>> list(libnum.sqrtmod(3, {2: 3}))
[7, 5, 1, 3]