(F, ring)
return sorted(H, key=lambda f: order(f.LM), reverse=True)
Computes a reduced Groebner basis for the ideal generated by F.

    f5b is an implementation of the F5B algorithm by Yao Sun and
    Dingkang Wang. Similarly to Buchberger's algorithm, the algorithm
    proceeds by computing critical pairs, computing the S-polynomial,
    reducing it and adjoining the reduced S-polynomial if it is not 0.

    Unlike Buchberger's algorithm, each polynomial contains additional
    information, namely a signature and a number. The signature
    specifies the path of computation (i.e. from which polynomial in
    the original basis was it derived and how), the number says when
    the polynomial was added to the basis.  With this information it
    is (often) possible to decide if an S-polynomial will reduce to
    0 and can be discarded.

    Optimizations include: Reducing the generators before computing
    a Groebner basis, removing redundant critical pairs when a new
    polynomial enters the basis and sorting the critical pairs and
    the current basis.

    Once a Groebner basis has been found, it gets reduced.

    ** References **
    Yao Sun, Dingkang Wang: "A New Proof for the Correctness of F5
    (F5-Like) Algorithm", http://arxiv.org/abs/1004.0084 (specifically
    v4)

    Thomas Becker, Volker Weispfenning, Groebner bases: A computational
    approach to commutative algebra, 1993, p. 203, 216
Computes a reduced Groebner basis for the ideal generated by F.
Computes a reduced Groebner basis for the ideal generated by F .
def _f5b(F, ring):
    """
    Computes a reduced Groebner basis for the ideal generated by F.

    f5b is an implementation of the F5B algorithm by Yao Sun and
    Dingkang Wang. Similarly to Buchberger's algorithm, the algorithm
    proceeds by computing critical pairs, computing the S-polynomial,
    reducing it and adjoining the reduced S-polynomial if it is not 0.

    Unlike Buchberger's algorithm, each polynomial contains additional
    information, namely a signature and a number. The signature
    specifies the path of computation (i.e. from which polynomial in
    the original basis was it derived and how), the number says when
    the polynomial was added to the basis.  With this information it
    is (often) possible to decide if an S-polynomial will reduce to
    0 and can be discarded.

    Optimizations include: Reducing the generators before computing
    a Groebner basis, removing redundant critical pairs when a new
    polynomial enters the basis and sorting the critical pairs and
    the current basis.

    Once a Groebner basis has been found, it gets reduced.

    ** References **
    Yao Sun, Dingkang Wang: "A New Proof for the Correctness of F5
    (F5-Like) Algorithm", http://arxiv.org/abs/1004.0084 (specifically
    v4)

    Thomas Becker, Volker Weispfenning, Groebner bases: A computational
    approach to commutative algebra, 1993, p. 203, 216
    """
    order = ring.order
    domain = ring.domain

    # reduce polynomials (like in Mario Pernici's implementation) (Becker, Weispfenning, p. 203)
    B = F
    while True:
        F = B
        B = []

        for i in xrange(len(F)):
            p = F[i]
            r = p.rem(F[:i])

            if r:
                B.append(r)

        if F == B:
            break

    # basis
    B = [lbp(sig(ring.zero_monom, i + 1), F[i], i + 1) for i in xrange(len(F))]
    B.sort(key=lambda f: order(Polyn(f).LM), reverse=True)

    # critical pairs
    CP = [critical_pair(B[i], B[j], ring) for i in xrange(len(B)) for j in xrange(i + 1, len(B))]
    CP.sort(key=lambda cp: cp_key(cp, ring), reverse=True)

    k = len(B)

    reductions_to_zero = 0

    while len(CP):
        cp = CP.pop()

        # discard redundant critical pairs:
        if is_rewritable_or_comparable(cp[0], Num(cp[2]), B):
            continue
        if is_rewritable_or_comparable(cp[3], Num(cp[5]), B):
            continue

        s = s_poly(cp)

        p = f5_reduce(s, B)

        p = lbp(Sign(p), Polyn(p).monic(), k + 1)

        if Polyn(p):
            # remove old critical pairs, that become redundant when adding p:
            indices = []
            for i, cp in enumerate(CP):
                if is_rewritable_or_comparable(cp[0], Num(cp[2]), [p]):
                    indices.append(i)
                elif is_rewritable_or_comparable(cp[3], Num(cp[5]), [p]):
                    indices.append(i)

            for i in reversed(indices):
                del CP[i]

            # only add new critical pairs that are not made redundant by p:
            for g in B:
                if Polyn(g):
                    cp = critical_pair(p, g, ring)
                    if is_rewritable_or_comparable(cp[0], Num(cp[2]), [p]):
                        continue
                    elif is_rewritable_or_comparable(cp[3], Num(cp[5]), [p]):
                        continue

                    CP.append(cp)

            # sort (other sorting methods/selection strategies were not as successful)
            CP.sort(key=lambda cp: cp_key(cp, ring), reverse=True)

            # insert p into B:
            m = Polyn(p).LM
            if order(m) <= order(Polyn(B[-1]).LM):
                B.append(p)
            else:
                for i, q in enumerate(B):
                    if order(m) > order(Polyn(q).LM):
                        B.insert(i, p)
                        break

            k += 1

            #print(len(B), len(CP), "%d critical pairs removed" % len(indices))
        else:
            reductions_to_zero += 1

    # reduce Groebner basis:
    H = [Polyn(g).monic() for g in B]
    H = red_groebner(H, ring)

    return sorted(H, key=lambda f: order(f.LM), reverse=True)
def _f5b ( F , ring ) : order = ring . order domain = ring . domain # reduce polynomials (like in Mario Pernici's implementation) (Becker, Weispfenning, p. 203) B = F while True : F = B B = [ ] for i in xrange ( len ( F ) ) : p = F [ i ] r = p . rem ( F [ : i ] ) if r : B . append ( r ) if F == B : break # basis B = [ lbp ( sig ( ring . zero_monom , i + 1 ) , F [ i ] , i + 1 ) for i in xrange ( len ( F ) ) ] B . sort ( key = lambda f : order ( Polyn ( f ) . LM ) , reverse = True ) # critical pairs CP = [ critical_pair ( B [ i ] , B [ j ] , ring ) for i in xrange ( len ( B ) ) for j in xrange ( i + 1 , len ( B ) ) ] CP . sort ( key = lambda cp : cp_key ( cp , ring ) , reverse = True ) k = len ( B ) reductions_to_zero = 0 while len ( CP ) : cp = CP . pop ( ) # discard redundant critical pairs: if is_rewritable_or_comparable ( cp [ 0 ] , Num ( cp [ 2 ] ) , B ) : continue if is_rewritable_or_comparable ( cp [ 3 ] , Num ( cp [ 5 ] ) , B ) : continue s = s_poly ( cp ) p = f5_reduce ( s , B ) p = lbp ( Sign ( p ) , Polyn ( p ) . monic ( ) , k + 1 ) if Polyn ( p ) : # remove old critical pairs, that become redundant when adding p: indices = [ ] for i , cp in enumerate ( CP ) : if is_rewritable_or_comparable ( cp [ 0 ] , Num ( cp [ 2 ] ) , [ p ] ) : indices . append ( i ) elif is_rewritable_or_comparable ( cp [ 3 ] , Num ( cp [ 5 ] ) , [ p ] ) : indices . append ( i ) for i in reversed ( indices ) : del CP [ i ] # only add new critical pairs that are not made redundant by p: for g in B : if Polyn ( g ) : cp = critical_pair ( p , g , ring ) if is_rewritable_or_comparable ( cp [ 0 ] , Num ( cp [ 2 ] ) , [ p ] ) : continue elif is_rewritable_or_comparable ( cp [ 3 ] , Num ( cp [ 5 ] ) , [ p ] ) : continue CP . append ( cp ) # sort (other sorting methods/selection strategies were not as successful) CP . sort ( key = lambda cp : cp_key ( cp , ring ) , reverse = True ) # insert p into B: m = Polyn ( p ) . LM if order ( m ) <= order ( Polyn ( B [ - 1 ] ) . LM ) : B . append ( p ) else : for i , q in enumerate ( B ) : if order ( m ) > order ( Polyn ( q ) . LM ) : B . insert ( i , p ) break k += 1 #print(len(B), len(CP), "%d critical pairs removed" % len(indices)) else : reductions_to_zero += 1 # reduce Groebner basis: H = [ Polyn ( g ) . monic ( ) for g in B ] H = red_groebner ( H , ring ) return sorted ( H , key = lambda f : order ( f . LM ) , reverse = True )