def dup_zz_cyclotomic_poly(n, K):
    """Efficiently generate n-th cyclotomic polnomial. """
    h = [K.one,-K.one]

    for p, k in factorint(n).iteritems():
        h = dup_quo(dup_inflate(h, p, K), h, K)
        h = dup_inflate(h, p**(k-1), K)

    return h

def test_dup_inflate():
    assert dup_inflate([], 17, ZZ) == []

    assert dup_inflate([1,2,3], 1, ZZ) == [1,2,3]
    assert dup_inflate([1,2,3], 2, ZZ) == [1,0,2,0,3]
    assert dup_inflate([1,2,3], 3, ZZ) == [1,0,0,2,0,0,3]
    assert dup_inflate([1,2,3], 4, ZZ) == [1,0,0,0,2,0,0,0,3]

    raises(IndexError, 'dup_inflate([1,2,3], 0, ZZ)')

def _dup_cyclotomic_decompose(n, K):
    H = [[K.one,-K.one]]

    for p, k in factorint(n).iteritems():
        Q = [ dup_quo(dup_inflate(h, p, K), h, K) for h in H ]
        H.extend(Q)

        for i in xrange(1, k):
            Q = [ dup_inflate(q, p, K) for q in Q ]
            H.extend(Q)

    return H