模块方程

解决二次和线性模方程的程序 ax^2 + bx + c = d (mod n) 其中 x 代表未知数，系数 a 到 d 每个都属于整数环 Z/nZ 的剩余类。模 n 必须是大于一的正整数。

如果有解，则解作为对应类中属于最小非负整数的剩余类给出。

安装

对于库目标，请在您的 Cargo.toml

[dependencies]
modular_equations = "1.0.5"

对于二进制目标，运行命令 cargo install modular_equations 并确保安装位置在 PATH 中。之后，命令 modular_equations --help 应该可以正常工作并显示进一步的使用建议。

使用

如下使用库来解决二次方程

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]);
}

线性模方程通常比二次方程更容易解决。以下代码块展示了解决一个最终没有解的线性方程的示例。

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

对于具有符号系数的线性方程，有类型 LinEqSigned 可用。

如果安装了二进制目标，可以使用 CLI 如下（解决与上面相同的二次方程）

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

方程的解将单独打印到 stdout。请注意，CLI 总是假设方程系数为有符号类型，模将取相应的无符号类型。这表明 CLI 不能接受超过 i128::MAX 的系数值作为方程的参数。

请注意，某些方程有大量的解，在这些情况下，求解器可能会显著减慢速度，甚至当解的数量超过 usize::MAX 时可能会崩溃。但这些都是非常特殊的情况，可能没有太多实际意义。

许可证

本程序根据 CC0v1 许可。