libnum icon indicating copy to clipboard operation
libnum copied to clipboard

Modular square root by power of 2

Open skunne opened this issue 2 years ago • 0 comments

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]

skunne avatar Mar 30 '23 10:03 skunne