(f, n, p, K)
return _sort_factors(factors, multiple=False)
Gathen-Shoup: Probabilistic Equal Degree Factorization

    Given a monic square-free polynomial ``f`` in ``GF(p)[x]`` and integer
    ``n`` such that ``n`` divides ``deg(f)``, returns all irreducible factors
    ``f_1,...,f_d`` of ``f``, each of degree ``n``. This is a complete
    factorization over Galois fields.

    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_edf_shoup

    >>> gf_edf_shoup(ZZ.map([1, 2837, 2277]), 1, 2917, ZZ)
    [[1, 852], [1, 1985]]

    References
    ==========

    1. [Shoup91]_
    2. [Gathen92]_
Gathen-Shoup: Probabilistic Equal Degree Factorization
Gathen - Shoup : Probabilistic Equal Degree Factorization
def gf_edf_shoup(f, n, p, K):
    """
    Gathen-Shoup: Probabilistic Equal Degree Factorization

    Given a monic square-free polynomial ``f`` in ``GF(p)[x]`` and integer
    ``n`` such that ``n`` divides ``deg(f)``, returns all irreducible factors
    ``f_1,...,f_d`` of ``f``, each of degree ``n``. This is a complete
    factorization over Galois fields.

    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_edf_shoup

    >>> gf_edf_shoup(ZZ.map([1, 2837, 2277]), 1, 2917, ZZ)
    [[1, 852], [1, 1985]]

    References
    ==========

    1. [Shoup91]_
    2. [Gathen92]_

    """
    N, q = gf_degree(f), int(p)

    if not N:
        return []
    if N <= n:
        return [f]

    factors, x = [f], [K.one, K.zero]

    r = gf_random(N - 1, p, K)

    if p == 2:
        h = gf_pow_mod(x, q, f, p, K)
        H = gf_trace_map(r, h, x, n - 1, f, p, K)[1]
        h1 = gf_gcd(f, H, p, K)
        h2 = gf_quo(f, h1, p, K)

        factors = gf_edf_shoup(h1, n, p, K) \
            + gf_edf_shoup(h2, n, p, K)
    else:
        b = gf_frobenius_monomial_base(f, p, K)
        H = _gf_trace_map(r, n, f, b, p, K)
        h = gf_pow_mod(H, (q - 1)//2, f, p, K)

        h1 = gf_gcd(f, h, p, K)
        h2 = gf_gcd(f, gf_sub_ground(h, K.one, p, K), p, K)
        h3 = gf_quo(f, gf_mul(h1, h2, p, K), p, K)

        factors = gf_edf_shoup(h1, n, p, K) \
            + gf_edf_shoup(h2, n, p, K) \
            + gf_edf_shoup(h3, n, p, K)

    return _sort_factors(factors, multiple=False)
def gf_edf_shoup ( f , n , p , K ) : N , q = gf_degree ( f ) , int ( p ) if not N : return [ ] if N <= n : return [ f ] factors , x = [ f ] , [ K . one , K . zero ] r = gf_random ( N - 1 , p , K ) if p == 2 : h = gf_pow_mod ( x , q , f , p , K ) H = gf_trace_map ( r , h , x , n - 1 , f , p , K ) [ 1 ] h1 = gf_gcd ( f , H , p , K ) h2 = gf_quo ( f , h1 , p , K ) factors = gf_edf_shoup ( h1 , n , p , K ) + gf_edf_shoup ( h2 , n , p , K ) else : b = gf_frobenius_monomial_base ( f , p , K ) H = _gf_trace_map ( r , n , f , b , p , K ) h = gf_pow_mod ( H , ( q - 1 ) // 2 , f , p , K ) h1 = gf_gcd ( f , h , p , K ) h2 = gf_gcd ( f , gf_sub_ground ( h , K . one , p , K ) , p , K ) h3 = gf_quo ( f , gf_mul ( h1 , h2 , p , K ) , p , K ) factors = gf_edf_shoup ( h1 , n , p , K ) + gf_edf_shoup ( h2 , n , p , K ) + gf_edf_shoup ( h3 , n , p , K ) return _sort_factors ( factors , multiple = False )