## bin+lib modular_equations

Program to solve quadratic and linear modular equations

### 6 stable releases

 1.0.5 Dec 29, 2022 Oct 27, 2022 Aug 12, 2022 Jun 4, 2022

#178 in Math

195KB
4.5K SLoC

# 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
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  is the only solution
assert_eq!(x, vec!);
}
``````

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.