ModularSquareRoots
Overview
This module provides support for finding modular square-roots.
In particular, for a given integer
To do this, you can use the function sqrtmod(n, m)
.
julia> using ModularSquareRoots
julia> sqrtmod(4, 5)
2-element Vector{Int64}:
3
2
julia> all(powermod(x, 2, 5) == 4 for x in sqrtmod(4, 5))
true
julia> sqrtmod(1240, 289032)
8-element Vector{Int64}:
107056
251572
10712
155228
278320
133804
181976
37460
julia> all(powermod(x, 2, 289032) == 1240 for x in sqrtmod(1240, 289032))
true
julia> sqrtmod(23, 200)
Int64[]
julia> !any(powermod(x, 2, 200) == 23 for x in sqrtmod(23, 200))
true
Prime Moduli
If you know that p = m
is prime,
then you can additionally use the function sqrtmodprime(n, p)
.
Note that there are no checks in sqrtmodprime
to ensure that p
is prime,
and the output of sqrtmodprime(n, p)
is undefined when p
is not prime.
The onus is on the user to use sqrtmodprime
correctly.
julia> sqrtmodprime(16, 101)
2-element Vector{Int64}:
97
4
julia> sqrtmodprime(15, 101)
Int64[]
julia> sqrtmodprime(0, 101)
1-element Vector{Int64}:
0