resultant

消去式のこと。なんかmagicallyに変数を減らすことができて便利。resultantの偉いところは合成数modでも使えるというところ（groebner basisがで動くのに対して）。別にグレブナー基底もで式を建ててから移せばいいんですけど

n = randint(0, 2^100)
Zn = Zmod(n)
s, t = Zn.random_element(), Zn.random_element()
u, v = s + t, s * t

PR.<x, y> = PolynomialRing(Zn)
f1 = x + y - u
f2 = x * y - v

# 理由はよくわからないけどchange_ringいる
PRz.<xz, yz> = PolynomialRing(Zn)
q1 = f1.change_ring(PRz)
q2 = f2.change_ring(PRz)

# ここで1変数の式に減らす
PRn.<xn> = PolynomialRing(Zn)
f = q1.resultant(q2) # xかyだけの式になる。どっちになるかは目で見る
f = f.univariate_polynomial().change_ring(PRn).subs(y=xn) # change_ringとかsubsとかいる
# ここでfはxnだけの式

2式のresultantはよく使うのでutility化してみた

def resultant(f1, f2, remove_var):
    """
    PR.<x, y> = PolynomialRing(Zmod(n))
    f1 = ...
    f2 = ...

    fn, xn = resultant(f1, f2, y) # yを消去する
    # fnはxnについての1変数多項式であることが期待できる
    """

    modulus = f1.base_ring().cardinality()
    gens = f1.parent().gens()
    assert len(gens) == 2
    gen_idx = list(gens).index(remove_var)

    gen_name = f1.parent().variable_names()[1 - gen_idx]
    namez = [name + "z" for name in f1.parent().variable_names()]
    namen = gen_name + "n"

    PRz = PolynomialRing(Zmod(modulus), namez)
    q1 = f1.change_ring(PRz)
    q2 = f2.change_ring(PRz)

    PRn = PolynomialRing(Zmod(modulus), [namen])
    xn = PRn.gen()
    f = q1.resultant(q2, gens[gen_idx])
    f = f.univariate_polynomial().change_ring(PRn).subs(**{gen_name: xn})
    return f, xn