Modular equations

Program to solve quadratic and linear modular equations ax^2 + bx + c = d (mod n) where x represents the unknown and coefficients from a to d residue classes each belonging to the ring of integers Z/nZ. Modulo n must be a positive integer and strictly larger than one.

Solutions, if any, are given as residue classes represented by the smallest nonnegative integers belonging to the corresponding classes.

Install

For the library target, add the following to your Cargo.toml

[dependencies]
modular_equations = "1.0.5"

For the binary target, run command cargo install modular_equations and make sure that the installation location is in PATH. After that the command modular_equations --help should work and show further usage advice.

Use

Use the library to solve quadratic equations as follows

use modular_equations::{QuadEq, QuadEqSigned};

// Solve equation x^2 + 3x + 4 = 0 (mod 2^60)
let quad_eq = QuadEq::<u64> {a: 1, b: 3, c: 4, d: 0, modu: 2u64.pow(60)};

// Method `solve` returns Option<Vec<T>>, T is now u64
if let Some(x) = quad_eq.solve() {
    // Check that the returned solution `x` is correct
    assert_eq!(x, vec![226_765_812_977_082_276, 926_155_691_629_764_697]);
}

// Solve equation -x^2 + 2x - 1 = 0 (mod n), modulo `n` is now a semiprime
// Coefs `a` and `c` are signed, hence must use signed type equation
let quad_eq = QuadEqSigned::<i128, u128> {
    a: -1,
    b: 2,
    c: -1,
    d: 0,
    modu: 2_082_064_493_491_567_088_228_629_031_592_644_077,
};

if let Some(x) = quad_eq.solve() {
    // Residue class [1] is the only solution
    assert_eq!(x, vec![1]);
}

Linear modular equations are generally much easier to solve than quadratic equations. Following code block shows an example of solving a linear equation that ultimately does not have any solutions.

use modular_equations::LinEq;

// Try to solve 17x = 1 (mod 255), or in other words find multip inverse for 17
let lin_eq = LinEq::<u8> {a: 17, b: 0, c: 1, modu: u8::MAX};

// 17 doesn't have multiplicative inverse in this case
assert_eq!(lin_eq.solve(), None);

For linear equations with signed coefficients there is type LinEqSigned available.

If the binary target was installed, CLI can be used as follows (solving the same quadratic equation as above)

modular_equations 1 3 4 0 $((2 ** 60))

Solutions for the equations are printed on their own lines to stdout. Notice that CLI always assumes a signed type for the equation coefficients and the modulo will take the corresponding unsigned type. This indicates that the CLI cannot take argument values above i128::MAX for coefficients of the equation.

Notice that some equations have a huge amount of solutions and in these cases the solver might slow down considerable or even panic when the solution count exceeds usize::MAX. But these are really special cases and probably not very much of interest.

License

This program is licensed under the CC0v1.