(f, p, K)
return factors
Kaltofen-Shoup: Deterministic Distinct Degree Factorization

    Given a monic square-free polynomial ``f`` in ``GF(p)[x]``, computes
    partial distinct degree factorization ``f_1,...,f_d`` of ``f`` where
    ``deg(f_i) != deg(f_j)`` for ``i != j``. The result is returned as a
    list of pairs ``(f_i, e_i)`` where ``deg(f_i) > 0`` and ``e_i > 0``
    is an argument to the equal degree factorization routine.

    This algorithm is an improved version of Zassenhaus algorithm for
    large ``deg(f)`` and modulus ``p`` (especially for ``deg(f) ~ lg(p)``).

    Examples
    ========

    >>> from sympy.polys.domains import ZZ
    >>> from sympy.polys.galoistools import gf_ddf_shoup, gf_from_dict

    >>> f = gf_from_dict({6: ZZ(1), 5: ZZ(-1), 4: ZZ(1), 3: ZZ(1), 1: ZZ(-1)}, 3, ZZ)

    >>> gf_ddf_shoup(f, 3, ZZ)
    [([1, 1, 0], 1), ([1, 1, 0, 1, 2], 2)]

    References
    ==========

    1. [Kaltofen98]_
    2. [Shoup95]_
    3. [Gathen92]_
Kaltofen-Shoup: Deterministic Distinct Degree Factorization
Kaltofen - Shoup : Deterministic Distinct Degree Factorization
def gf_ddf_shoup(f, p, K):
    """
    Kaltofen-Shoup: Deterministic Distinct Degree Factorization

    Given a monic square-free polynomial ``f`` in ``GF(p)[x]``, computes
    partial distinct degree factorization ``f_1,...,f_d`` of ``f`` where
    ``deg(f_i) != deg(f_j)`` for ``i != j``. The result is returned as a
    list of pairs ``(f_i, e_i)`` where ``deg(f_i) > 0`` and ``e_i > 0``
    is an argument to the equal degree factorization routine.

    This algorithm is an improved version of Zassenhaus algorithm for
    large ``deg(f)`` and modulus ``p`` (especially for ``deg(f) ~ lg(p)``).

    Examples
    ========

    >>> from sympy.polys.domains import ZZ
    >>> from sympy.polys.galoistools import gf_ddf_shoup, gf_from_dict

    >>> f = gf_from_dict({6: ZZ(1), 5: ZZ(-1), 4: ZZ(1), 3: ZZ(1), 1: ZZ(-1)}, 3, ZZ)

    >>> gf_ddf_shoup(f, 3, ZZ)
    [([1, 1, 0], 1), ([1, 1, 0, 1, 2], 2)]

    References
    ==========

    1. [Kaltofen98]_
    2. [Shoup95]_
    3. [Gathen92]_

    """
    n = gf_degree(f)
    k = int(_ceil(_sqrt(n//2)))
    b = gf_frobenius_monomial_base(f, p, K)
    h = gf_frobenius_map([K.one, K.zero], f, b, p, K)
    # U[i] = x**(p**i)
    U = [[K.one, K.zero], h] + [K.zero]*(k - 1)

    for i in xrange(2, k + 1):
        U[i] = gf_frobenius_map(U[i-1], f, b, p, K)

    h, U = U[k], U[:k]
    # V[i] = x**(p**(k*(i+1)))
    V = [h] + [K.zero]*(k - 1)

    for i in xrange(1, k):
        V[i] = gf_compose_mod(V[i - 1], h, f, p, K)

    factors = []

    for i, v in enumerate(V):
        h, j = [K.one], k - 1

        for u in U:
            g = gf_sub(v, u, p, K)
            h = gf_mul(h, g, p, K)
            h = gf_rem(h, f, p, K)

        g = gf_gcd(f, h, p, K)
        f = gf_quo(f, g, p, K)

        for u in reversed(U):
            h = gf_sub(v, u, p, K)
            F = gf_gcd(g, h, p, K)

            if F != [K.one]:
                factors.append((F, k*(i + 1) - j))

            g, j = gf_quo(g, F, p, K), j - 1

    if f != [K.one]:
        factors.append((f, gf_degree(f)))

    return factors
def gf_ddf_shoup ( f , p , K ) : n = gf_degree ( f ) k = int ( _ceil ( _sqrt ( n // 2 ) ) ) b = gf_frobenius_monomial_base ( f , p , K ) h = gf_frobenius_map ( [ K . one , K . zero ] , f , b , p , K ) # U[i] = x**(p**i) U = [ [ K . one , K . zero ] , h ] + [ K . zero ] * ( k - 1 ) for i in xrange ( 2 , k + 1 ) : U [ i ] = gf_frobenius_map ( U [ i - 1 ] , f , b , p , K ) h , U = U [ k ] , U [ : k ] # V[i] = x**(p**(k*(i+1))) V = [ h ] + [ K . zero ] * ( k - 1 ) for i in xrange ( 1 , k ) : V [ i ] = gf_compose_mod ( V [ i - 1 ] , h , f , p , K ) factors = [ ] for i , v in enumerate ( V ) : h , j = [ K . one ] , k - 1 for u in U : g = gf_sub ( v , u , p , K ) h = gf_mul ( h , g , p , K ) h = gf_rem ( h , f , p , K ) g = gf_gcd ( f , h , p , K ) f = gf_quo ( f , g , p , K ) for u in reversed ( U ) : h = gf_sub ( v , u , p , K ) F = gf_gcd ( g , h , p , K ) if F != [ K . one ] : factors . append ( ( F , k * ( i + 1 ) - j ) ) g , j = gf_quo ( g , F , p , K ) , j - 1 if f != [ K . one ] : factors . append ( ( f , gf_degree ( f ) ) ) return factors