### 6 stable releases

1.0.5 | Dec 29, 2022 |
---|---|

1.0.4 | Oct 27, 2022 |

1.0.3 | Aug 12, 2022 |

1.0.1 | Jun 4, 2022 |

#**178** in Math

**CC0**license

195KB

4.5K
SLoC

# Modular equations

Program to solve quadratic and linear modular equations

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.`ax ^2 + bx + c = d (mod n)`

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

and make sure that the installation location is in PATH. After that the command `cargo`` install modular_equations`

should work and show further usage advice.`modular_equations --help`

## 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`:` `2``u64``.``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

available.`LinEqSigned`

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.

#### Dependencies

~1MB

~21K SLoC