#!/usr/bin/ruby

# Tests for the built-in `Mod(n,m)` class.

do {
    var a = Mod(13, 19)

    assert_eq(23 % Mod(9,97), 23%9)
    assert_eq(cyclotomic(Mod(-23, 863*503), 43), cyclotomicmod(43, -23, 863*503))

    assert_eq(a, Mod(13, 19))
    a += 15    # Mod(9, 19)
    assert_eq(a, Mod(9, 19))
    a *= 99    # Mod(17, 19)
    assert_eq(a, Mod(17, 19))
    a /= 17    # Mod(1, 19)
    assert_eq(a, Mod(1, 19))
    assert(a == 1)

    a -= 43    # Mod(15, 19)
    assert_eq(a, Mod(15, 19))

    assert_eq(a**42, Mod(11, 19))       # Mod(11, 19)
    assert_eq(a**(-1), Mod(14, 19))     # Mod(14, 19)
    assert_eq(sqrt(a+1), Mod(4, 19))    # Mod(4, 19)

    assert_eq(Mod(3/4, 4171)**1234, Mod(2138, 4171))
    assert_eq(Mod(3/4, 4171)**(-1234), Mod(2304, 4171))

    assert_eq(powmod(3/4, 1234, 4171), 2138)
    assert_eq(powmod(43/97, -129,  57 * 123), 3970)
    assert_eq(powmod(3/4, -1234, 4171), 2304)

    assert_eq(Mod(3/4, 4171)**(1234), Mod(2138, 4171))
    assert_eq(Mod(43/97, 57 * 123)**(-129), Mod(3970, 57*123))
    assert_eq(Mod(3/4, 4171)**(-1234), Mod(2304, 4171))

    assert_eq(powmod(43/97, 127, 43),     0)
    assert_eq(powmod(43/97, 127, 43 * 2), 43)
    assert(powmod(43/97, 127, 97 * 3) -> is_nan)

    assert_eq(Mod(43/97, 43)**127,     0)
    assert_eq(Mod(43/97, 43 * 2)**127, 43)
    assert(Mod(43/97, 97 * 3)**128 -> lift.is_nan)

    assert_eq(Mod(182398124/123124124, 4171)**(-3), Mod(1970, 4171))
    assert_eq(Mod(182398124/123124124, 4171)**(-5), Mod(3635, 4171))

    assert_eq(chinese(Mod(43, 19), Mod(13, 41)), Mod(423, 779))   # Mod(423, 779)

    with (1e10.irand, 1e10.irand) {|n, m|
        assert_eq(
            Mod(Matrix([1,1],[1,0]), m)**n,
            Mod(Matrix(
                [fibmod(n+1, m), fibmod(n, m)]
                [fibmod(n, m), fibmod(n-1, m)]), m)
        )
    }

    var m = random_prime(1e5)

    var x = 9
    var y = 10

    var A = Matrix.build(x, y, { 1e7.irand })
    var B = Matrix.build(x, y, { 1e7.irand })

    assert_eq(Mod(A, m) + B, Mod((A + B)%m, m))
    assert_eq(Mod(A, m) - B, Mod((A - B)%m, m))
    assert_eq(Mod(A, m) * B, Mod((A * B)%m, m))
    assert_eq(Mod(A, m) & B, Mod((A%m & B%m), m))
    assert_eq(Mod(A, m) | B, Mod((A%m | B%m), m))
    assert_eq(Mod(A, m) ^ B, Mod((A%m ^ B%m), m))

    assert_eq(Mod(A, m) + Mod(B, m), Mod((A + B)%m, m))
    assert_eq(Mod(A, m) & Mod(B, m), Mod((A%m & B%m), m))

    assert_eq((3 + Mod(4, 5)), Mod(2, 5))
    assert_eq((3 - Mod(4, 5)), Mod(4, 5))
    assert_eq((3 * Mod(4, 5)), Mod(2, 5))
    assert_eq((3 / Mod(4, 5)), Mod(2, 5))

    assert_eq(Mod(A, m) / B, Mod(A * B.invmod(m), m))

    assert_eq(A.inv.flat.map{.mod(m)}, A.invmod(m).flat)
    assert_eq(B.inv.flat.map{.mod(m)}, B.powmod(-1, m).flat)
    assert_eq(B.inv**2 -> flat.map{.mod(m)}, B.powmod(-2, m).flat)
}

do {
    var n = 1e40.random_prime

    assert_eq(Mod(2, n)**n, 2)
    assert_eq(Mod(2, n)**(n-1), 1)

    assert_eq(Gauss(Mod(2, n), 0)**(n-1), 1)
    assert_eq(Gauss(Mod(2, n), Mod(0, n))**(n-1), 1)
    assert_eq(Gauss(Mod(3, n), 0)**n, 3)

    assert_eq(Quadratic(Mod(3, n))**n, 3)
    assert_eq(Quadratic(Mod(3, n))**(n-1), 1)

    assert_eq(Quaternion(Mod(3, n))**n, 3)
    assert_eq(Quaternion(Mod(3, n))**(n-1), 1)

    assert_eq(Mod(Fraction(2, 1), n)**n, 2)
    assert_eq(Mod(Fraction(2, 1), n)**(n-1), 1)
    assert_eq(Mod(Fraction(2, 1), Fraction(n, 1))**n, 2)
    assert_eq(Mod(Fraction(2, 1), Fraction(n, 1))**(n-1), 1)

    assert_eq(Fraction(Mod(2, n), Mod(1, n))**n, 2)
    assert_eq(Fraction(Mod(2, n), Mod(1, n))**(n-1), 1)

    assert_eq(Fraction(Mod(2, n), 1)**n, 2)
    assert_eq(Fraction(Mod(2, n), 1)**(n-1), 1)

    assert_eq(Fraction(Mod(2, n), 1.rat)**n, 2)
    assert_eq(Fraction(Mod(2, n), 1.rat)**(n-1), 1)
}

say "** Test passed!"