Skip to content

Modular square root by power of 2 #14

@skunne

Description

@skunne

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]

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions