def dmp_zz_wang_hensel_lifting(f, H, LC, A, p, u, K):
    """Wang/EEZ: Parallel Hensel lifting algorithm. """
    S, n, v = [f], len(A), u-1

    H = list(H)

    for i, a in enumerate(reversed(A[1:])):
        s = dmp_eval_in(S[0], a, n-i, u-i, K)
        S.insert(0, dmp_ground_trunc(s, p, v-i, K))

    d = max(dmp_degree_list(f, u)[1:])

    for j, s, a in zip(xrange(2, n+2), S, A):
        G, w = list(H), j-1

        I, J = A[:j-2], A[j-1:]

        for i, (h, lc) in enumerate(zip(H, LC)):
            lc = dmp_ground_trunc(dmp_eval_tail(lc, J, v, K), p, w-1, K)
            H[i] = [lc] + dmp_raise(h[1:], 1, w-1, K)

        m = dmp_nest([K.one, -a], w, K)
        M = dmp_one(w, K)

        c = dmp_sub(s, dmp_expand(H, w, K), w, K)

        dj = dmp_degree_in(s, w, w)

        for k in xrange(0, dj):
            if dmp_zero_p(c, w):
                break

            M = dmp_mul(M, m, w, K)
            C = dmp_diff_eval_in(c, k+1, a, w, w, K)

            if not dmp_zero_p(C, w-1):
                C = dmp_quo_ground(C, K.factorial(k+1), w-1, K)
                T = dmp_zz_diophantine(G, C, I, d, p, w-1, K)

                for i, (h, t) in enumerate(zip(H, T)):
                    h = dmp_add_mul(h, dmp_raise(t, 1, w-1, K), M, w, K)
                    H[i] = dmp_ground_trunc(h, p, w, K)

                h = dmp_sub(s, dmp_expand(H, w, K), w, K)
                c = dmp_ground_trunc(h, p, w, K)

    if dmp_expand(H, u, K) != f:
        raise ExtraneousFactors # pragma: no cover
    else:
        return H

def dmp_lift(f, u, K):
    """
    Convert algebraic coefficients to integers in ``K[X]``.

    Examples
    ========

    >>> from sympy.polys import ring, QQ
    >>> from sympy import I

    >>> K = QQ.algebraic_field(I)
    >>> R, x = ring("x", K)

    >>> f = x**2 + K([QQ(1), QQ(0)])*x + K([QQ(2), QQ(0)])

    >>> R.dmp_lift(f)
    x**8 + 2*x**6 + 9*x**4 - 8*x**2 + 16

    """
    if not K.is_Algebraic:
        raise DomainError(
            'computation can be done only in an algebraic domain')

    F, monoms, polys = dmp_to_dict(f, u), [], []

    for monom, coeff in F.items():
        if not coeff.is_ground:
            monoms.append(monom)

    perms = variations([-1, 1], len(monoms), repetition=True)

    for perm in perms:
        G = dict(F)

        for sign, monom in zip(perm, monoms):
            if sign == -1:
                G[monom] = -G[monom]

        polys.append(dmp_from_dict(G, u, K))

    return dmp_convert(dmp_expand(polys, u, K), u, K, K.dom)

def dmp_lift(f, u, K):
    """
    Convert algebraic coefficients to integers in ``K[X]``.

    Examples
    ========

    >>> from sympy import I
    >>> from sympy.polys.domains import QQ
    >>> from sympy.polys.densetools import dmp_lift

    >>> K = QQ.algebraic_field(I)
    >>> f = [K(1), K([QQ(1), QQ(0)]), K([QQ(2), QQ(0)])]

    >>> dmp_lift(f, 0, K)
    [1/1, 0/1, 2/1, 0/1, 9/1, 0/1, -8/1, 0/1, 16/1]

    """
    if not K.is_Algebraic:
        raise DomainError(
            'computation can be done only in an algebraic domain')

    F, monoms, polys = dmp_to_dict(f, u), [], []

    for monom, coeff in F.iteritems():
        if not coeff.is_ground:
            monoms.append(monom)

    perms = variations([-1, 1], len(monoms), repetition=True)

    for perm in perms:
        G = dict(F)

        for sign, monom in zip(perm, monoms):
            if sign == -1:
                G[monom] = -G[monom]

        polys.append(dmp_from_dict(G, u, K))

    return dmp_convert(dmp_expand(polys, u, K), u, K, K.dom)

def dmp_zz_diophantine(F, c, A, d, p, u, K):
    """Wang/EEZ: Solve multivariate Diophantine equations. """
    if not A:
        S = [ [] for _ in F ]
        n = dup_degree(c)

        for i, coeff in enumerate(c):
            if not coeff:
                continue

            T = dup_zz_diophantine(F, n-i, p, K)

            for j, (s, t) in enumerate(zip(S, T)):
                t = dup_mul_ground(t, coeff, K)
                S[j] = dup_trunc(dup_add(s, t, K), p, K)
    else:
        n = len(A)
        e = dmp_expand(F, u, K)

        a, A = A[-1], A[:-1]
        B, G = [], []

        for f in F:
            B.append(dmp_quo(e, f, u, K))
            G.append(dmp_eval_in(f, a, n, u, K))

        C = dmp_eval_in(c, a, n, u, K)

        v = u - 1

        S = dmp_zz_diophantine(G, C, A, d, p, v, K)
        S = [ dmp_raise(s, 1, v, K) for s in S ]

        for s, b in zip(S, B):
            c = dmp_sub_mul(c, s, b, u, K)

        c = dmp_ground_trunc(c, p, u, K)

        m = dmp_nest([K.one, -a], n, K)
        M = dmp_one(n, K)

        for k in xrange(0, d):
            if dmp_zero_p(c, u):
                break

            M = dmp_mul(M, m, u, K)
            C = dmp_diff_eval_in(c, k+1, a, n, u, K)

            if not dmp_zero_p(C, v):
                C = dmp_quo_ground(C, K.factorial(k+1), v, K)
                T = dmp_zz_diophantine(G, C, A, d, p, v, K)

                for i, t in enumerate(T):
                    T[i] = dmp_mul(dmp_raise(t, 1, v, K), M, u, K)

                for i, (s, t) in enumerate(zip(S, T)):
                    S[i] = dmp_add(s, t, u, K)

                for t, b in zip(T, B):
                    c = dmp_sub_mul(c, t, b, u, K)

                c = dmp_ground_trunc(c, p, u, K)

        S = [ dmp_ground_trunc(s, p, u, K) for s in S ]

    return S

def test_dmp_expand():
    assert dmp_expand((), 1, ZZ) == [[1]]
    assert dmp_expand(([[1],[2],[3]], [[1],[2]], [[7],[5],[4],[3]]), 1, ZZ) == \
        dmp_mul([[1],[2],[3]], dmp_mul([[1],[2]], [[7],[5],[4],[3]], 1, ZZ), 1, ZZ)

def test_dmp_zz_wang():
    p = ZZ(nextprime(dmp_zz_mignotte_bound(w_1, 2, ZZ)))

    assert p == ZZ(6291469)

    t_1, k_1, e_1 = dmp_normal([[1],[]], 1, ZZ), 1, ZZ(-14)
    t_2, k_2, e_2 = dmp_normal([[1, 0]], 1, ZZ), 2, ZZ(3)
    t_3, k_3, e_3 = dmp_normal([[1],[ 1, 0]], 1, ZZ), 2, ZZ(-11)
    t_4, k_4, e_4 = dmp_normal([[1],[-1, 0]], 1, ZZ), 1, ZZ(-17)

    T = [t_1, t_2, t_3, t_4]
    K = [k_1, k_2, k_3, k_4]
    E = [e_1, e_2, e_3, e_4]

    T = zip(T, K)

    A = [ZZ(-14), ZZ(3)]

    S = dmp_eval_tail(w_1, A, 2, ZZ)
    cs, s = dup_primitive(S, ZZ)

    assert cs == 1 and s == S == \
        dup_normal([1036728, 915552, 55748, 105621, -17304, -26841, -644], ZZ)

    assert dmp_zz_wang_non_divisors(E, cs, 4, ZZ) == [7, 3, 11, 17]
    assert dup_sqf_p(s, ZZ) and dup_degree(s) == dmp_degree(w_1, 2)

    _, H = dup_zz_factor_sqf(s, ZZ)

    h_1 = dup_normal([44,  42,   1], ZZ)
    h_2 = dup_normal([126, -9,  28], ZZ)
    h_3 = dup_normal([187,  0, -23], ZZ)

    assert H == [h_1, h_2, h_3]

    lc_1 = dmp_normal([[-4], [-4,0]], 1, ZZ)
    lc_2 = dmp_normal([[-1,0,0], []], 1, ZZ)
    lc_3 = dmp_normal([[1], [], [-1,0,0]], 1, ZZ)

    LC = [lc_1, lc_2, lc_3]

    assert dmp_zz_wang_lead_coeffs(w_1, T, cs, E, H, A, 2, ZZ) == (w_1, H, LC)

    H_1 = [ dmp_normal(t, 0, ZZ) for t in [[44L,42L,1L],[126L,-9L,28L],[187L,0L,-23L]] ]
    H_2 = [ dmp_normal(t, 1, ZZ) for t in [[[-4,-12],[-3,0],[1]],[[-9,0],[-9],[-2,0]],[[1,0,-9],[],[1,-9]]] ]
    H_3 = [ dmp_normal(t, 1, ZZ) for t in [[[-4,-12],[-3,0],[1]],[[-9,0],[-9],[-2,0]],[[1,0,-9],[],[1,-9]]] ]

    c_1 = dmp_normal([-70686,-5863,-17826,2009,5031,74], 0, ZZ)
    c_2 = dmp_normal([[9,12,-45,-108,-324],[18,-216,-810,0],[2,9,-252,-288,-945],[-30,-414,0],[2,-54,-3,81],[12,0]], 1, ZZ)
    c_3 = dmp_normal([[-36,-108,0],[-27,-36,-108],[-8,-42,0],[-6,0,9],[2,0]], 1, ZZ)

    T_1 = [ dmp_normal(t, 0, ZZ) for t in [[-3,0],[-2],[1]] ]
    T_2 = [ dmp_normal(t, 1, ZZ) for t in [[[-1,0],[]],[[-3],[]],[[-6]]] ]
    T_3 = [ dmp_normal(t, 1, ZZ) for t in [[[]],[[]],[[-1]]] ]

    assert dmp_zz_diophantine(H_1, c_1,        [], 5, p, 0, ZZ) == T_1
    assert dmp_zz_diophantine(H_2, c_2, [ZZ(-14)], 5, p, 1, ZZ) == T_2
    assert dmp_zz_diophantine(H_3, c_3, [ZZ(-14)], 5, p, 1, ZZ) == T_3

    factors = dmp_zz_wang_hensel_lifting(w_1, H, LC, A, p, 2, ZZ)

    assert dmp_expand(factors, 2, ZZ) == w_1