sidef-scripts/Math/solve_modular_quadratic_equation.sf

#!/usr/bin/ruby

# Author: Trizen
# Date: 27 April 2022
# Edit: 26 October 2023
# https://github.com/trizen

# Solve modular quadratic equations of the form:
#   a*x^2 + b*x + c == 0 (mod m)

# Solving method:
#   D = b^2 - 4*a*c
#   t^2 == D (mod 4*a*m)

# By finding all the solutions to `t`, using `sqrtmod(D, 4*a*m)`, the candidate values for `x` are given by:
#   x_1 = (-b + t)/(2*a)
#   x_2 = (-b - t)/(2*a)

func modular_quadratic_equation (a,b,c,m) {

    a %= m
    b %= m
    c %= m

    var D = (b**2 - 4*a*c).mod(4*a*m)
    var S = []

    for t in (sqrtmod_all(D, 4*a*m)) {
        for u,v in ([[-b + t, 2*a]]) {
            var x = (u/v)%m
            assert_eq((a*x*x + b*x + c)%m, 0)
            S << x
        }
    }

    return S.uniq.sort
}

say modular_quadratic_equation(1,1,-1e10 + 8,1e10)
say modular_quadratic_equation(4,6,10 - 1e10, 1e10)
say modular_quadratic_equation(1,1,-1e10 - 10, 1e10)

assert_eq(modular_quadratic_equation(3,4,5, 124),         %n[47, 55, 109, 117])
assert_eq(modular_quadratic_equation(3/5,4,5,124),        %n[19, 57, 81, 119])
assert_eq(modular_quadratic_equation(3/13, 112, 13, 124), %n[9, 43, 71, 105])
assert_eq(modular_quadratic_equation(3/13, 4, 13*5, 124), %n[33, 53, 95, 115])
assert_eq(modular_quadratic_equation(3/13, 4, 5, 124),    %n[3, 21, 65, 83])
assert_eq(modular_quadratic_equation(3/13, 4/7, 5, 124),  %n[5, 25, 67, 87])
assert_eq(modular_quadratic_equation(400, 85, 125, 1600), [1983/80, 2035/16, 963/5, 295, 27583/80, 7155/16, 2563/5, 615, 53183/80, 12275/16, 4163/5, 935, 78783/80, 17395/16, 5763/5, 1255, 104383/80, 22515/16, 7363/5, 1575])

__END__
[1810486343, 2632873031, 7367126968, 8189513656]
[905243171, 1316436515, 7367126967/2, 8189513655/2, 5905243171, 6316436515, 17367126967/2, 18189513655/2]
[263226214, 1620648089, 8379351910, 9736773785]