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 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

toml [dependencies] modular_equations = "^1.0"

For the binary target, easiest way to install is just to run 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

After installation, use the library to solve quadratic equations as follows

```rust use modular_equations::{QuadEq, QuadEqSigned};

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

// Method solve returns Option>, T is now u64 if let Some(x) = quadeq.solve() { // Check that the returned solution x is correct asserteq!(x, vec![226765812977082276, 926155691629764697]); }

// Solve equation -x^2 + 2x - 1 = 0 (mod n), n is now a semiprime // Coefs a and c are signed, hence use signed type equation let quadeq = QuadEqSigned:: { a: -1, b: 2, c: -1, d: 0, modu: 2082064493491567088228629031592644_077, };

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

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

```rust use modular_equations::LinEq;

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

// 17 doesn't have multiplicative inverse in this case asserteq!(lineq.solve(), None); ```

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

Command line usage is simple as the following example of solving the same quadratic equation as above indicates

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

Solutions for the equation 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 usually not very much of interest.

License

This program is licensed under the CC0v1.