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 $\mathbb{Z}/n\mathbb{Z}$. 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. Then 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 + 2 = 0 (mod 2^30) let quad_eq = QuadEq:: {a: 1, b: 3, c: 2, d: 0, modu: 2u32.pow(30)};

if let Some(x) = quadeq.solve() { // Test that the returned solution x is correct asserteq!(x, vec![1073741822, 1073741823]); }

// Solve other equation -x^2 + 2x - 1 = 0 (mod n), where modulo n is now a semiprime // Coefs a and c are signed, hence must use signed type equation (both types must have the same size in bytes!) 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 equation 17x = 1 (mod 255), which basically tries to find the multiplicative inverse of 17 in Z/255Z let lin_eq = LinEq:: {a: 17, b: 0, c: 1, modu: u8::MAX};

// As 17 doesn't have multiplicative inverse in this case, there aren't solutions for the equation asserteq!(lineq.solve(), None); ```

CLI usage should also be simple as the following example of solving the same quadratic equation as above indicates

bash modular_equations 1 3 2 0 $((2 ** 30))

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.

License

This program is licensed under the CC0v1.