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

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

    Consider the square-free polynomial ``f = x**3 + x**2 + x + 1`` in
    ``GF(5)[x]``. Let's compute its irreducible factors of degree one::

       >>> from sympy.polys.domains import ZZ
       >>> from sympy.polys.galoistools import gf_edf_zassenhaus

       >>> gf_edf_zassenhaus([1,1,1,1], 1, 5, ZZ)
       [[1, 1], [1, 2], [1, 3]]

    References
    ==========

    1. [Gathen99]_
    2. [Geddes92]_
Cantor-Zassenhaus: Probabilistic Equal Degree Factorization
Cantor - Zassenhaus : Probabilistic Equal Degree Factorization
def gf_edf_zassenhaus(f, n, p, K):
    """
    Cantor-Zassenhaus: Probabilistic Equal Degree Factorization

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

    Consider the square-free polynomial ``f = x**3 + x**2 + x + 1`` in
    ``GF(5)[x]``. Let's compute its irreducible factors of degree one::

       >>> from sympy.polys.domains import ZZ
       >>> from sympy.polys.galoistools import gf_edf_zassenhaus

       >>> gf_edf_zassenhaus([1,1,1,1], 1, 5, ZZ)
       [[1, 1], [1, 2], [1, 3]]

    References
    ==========

    1. [Gathen99]_
    2. [Geddes92]_

    """
    factors, q = [f], int(p)

    if gf_degree(f) <= n:
        return factors

    N = gf_degree(f) // n
    if p != 2:
        b = gf_frobenius_monomial_base(f, p, K)

    while len(factors) < N:
        r = gf_random(2*n - 1, p, K)

        if p == 2:
            h = r

            for i in xrange(0, 2**(n*N - 1)):
                r = gf_pow_mod(r, 2, f, p, K)
                h = gf_add(h, r, p, K)

            g = gf_gcd(f, h, p, K)
        else:
            h = _gf_pow_pnm1d2(r, n, f, b, p, K)
            g = gf_gcd(f, gf_sub_ground(h, K.one, p, K), p, K)

        if g != [K.one] and g != f:
            factors = gf_edf_zassenhaus(g, n, p, K) \
                + gf_edf_zassenhaus(gf_quo(f, g, p, K), n, p, K)

    return _sort_factors(factors, multiple=False)
def gf_edf_zassenhaus ( f , n , p , K ) : factors , q = [ f ] , int ( p ) if gf_degree ( f ) <= n : return factors N = gf_degree ( f ) // n if p != 2 : b = gf_frobenius_monomial_base ( f , p , K ) while len ( factors ) < N : r = gf_random ( 2 * n - 1 , p , K ) if p == 2 : h = r for i in xrange ( 0 , 2 ** ( n * N - 1 ) ) : r = gf_pow_mod ( r , 2 , f , p , K ) h = gf_add ( h , r , p , K ) g = gf_gcd ( f , h , p , K ) else : h = _gf_pow_pnm1d2 ( r , n , f , b , p , K ) g = gf_gcd ( f , gf_sub_ground ( h , K . one , p , K ) , p , K ) if g != [ K . one ] and g != f : factors = gf_edf_zassenhaus ( g , n , p , K ) + gf_edf_zassenhaus ( gf_quo ( f , g , p , K ) , n , p , K ) return _sort_factors ( factors , multiple = False )