(ex, x, cls)
return result
Computes the minimal polynomial of an algebraic number
    using Groebner bases

    Examples
    ========

    >>> from sympy import minimal_polynomial, sqrt, Rational
    >>> from sympy.abc import x
    >>> minimal_polynomial(sqrt(2) + 3*Rational(1, 3), x, compose=False)
    x**2 - 2*x - 1
Computes the minimal polynomial of an algebraic number
    using Groebner bases
Computes the minimal polynomial of an algebraic number using Groebner bases
def _minpoly_groebner(ex, x, cls):
    """
    Computes the minimal polynomial of an algebraic number
    using Groebner bases

    Examples
    ========

    >>> from sympy import minimal_polynomial, sqrt, Rational
    >>> from sympy.abc import x
    >>> minimal_polynomial(sqrt(2) + 3*Rational(1, 3), x, compose=False)
    x**2 - 2*x - 1

    """
    from sympy.polys.polytools import degree
    from sympy.core.function import expand_multinomial

    generator = numbered_symbols('a', cls=Dummy)
    mapping, symbols, replace = {}, {}, []

    def update_mapping(ex, exp, base=None):
        a = next(generator)
        symbols[ex] = a

        if base is not None:
            mapping[ex] = a**exp + base
        else:
            mapping[ex] = exp.as_expr(a)

        return a

    def bottom_up_scan(ex):
        if ex.is_Atom:
            if ex is S.ImaginaryUnit:
                if ex not in mapping:
                    return update_mapping(ex, 2, 1)
                else:
                    return symbols[ex]
            elif ex.is_Rational:
                return ex
        elif ex.is_Add:
            return Add(*[ bottom_up_scan(g) for g in ex.args ])
        elif ex.is_Mul:
            return Mul(*[ bottom_up_scan(g) for g in ex.args ])
        elif ex.is_Pow:
            if ex.exp.is_Rational:
                if ex.exp < 0 and ex.base.is_Add:
                    coeff, terms = ex.base.as_coeff_add()
                    elt, _ = primitive_element(terms, polys=True)

                    alg = ex.base - coeff

                    # XXX: turn this into eval()
                    inverse = invert(elt.gen + coeff, elt).as_expr()
                    base = inverse.subs(elt.gen, alg).expand()

                    if ex.exp == -1:
                        return bottom_up_scan(base)
                    else:
                        ex = base**(-ex.exp)
                if not ex.exp.is_Integer:
                    base, exp = (
                        ex.base**ex.exp.p).expand(), Rational(1, ex.exp.q)
                else:
                    base, exp = ex.base, ex.exp
                base = bottom_up_scan(base)
                expr = base**exp

                if expr not in mapping:
                    return update_mapping(expr, 1/exp, -base)
                else:
                    return symbols[expr]
        elif ex.is_AlgebraicNumber:
            if ex.root not in mapping:
                return update_mapping(ex.root, ex.minpoly)
            else:
                return symbols[ex.root]

        raise NotAlgebraic("%s doesn't seem to be an algebraic number" % ex)

    def simpler_inverse(ex):
        """
        Returns True if it is more likely that the minimal polynomial
        algorithm works better with the inverse
        """
        if ex.is_Pow:
            if (1/ex.exp).is_integer and ex.exp < 0:
                if ex.base.is_Add:
                    return True
        if ex.is_Mul:
            hit = True
            a = []
            for p in ex.args:
                if p.is_Add:
                    return False
                if p.is_Pow:
                    if p.base.is_Add and p.exp > 0:
                        return False

            if hit:
                return True
        return False

    inverted = False
    ex = expand_multinomial(ex)
    if ex.is_AlgebraicNumber:
        return ex.minpoly.as_expr(x)
    elif ex.is_Rational:
        result = ex.q*x - ex.p
    else:
        inverted = simpler_inverse(ex)
        if inverted:
            ex = ex**-1
        res = None
        if ex.is_Pow and (1/ex.exp).is_Integer:
            n = 1/ex.exp
            res = _minimal_polynomial_sq(ex.base, n, x)

        elif _is_sum_surds(ex):
            res = _minimal_polynomial_sq(ex, S.One, x)

        if res is not None:
            result = res

        if res is None:
            bus = bottom_up_scan(ex)
            F = [x - bus] + list(mapping.values())
            G = groebner(F, list(symbols.values()) + [x], order='lex')

            _, factors = factor_list(G[-1])
            # by construction G[-1] has root `ex`
            result = _choose_factor(factors, x, ex)
    if inverted:
        result = _invertx(result, x)
        if result.coeff(x**degree(result, x)) < 0:
            result = expand_mul(-result)

    return result
def _minpoly_groebner ( ex , x , cls ) : from sympy . polys . polytools import degree from sympy . core . function import expand_multinomial generator = numbered_symbols ( 'a' , cls = Dummy ) mapping , symbols , replace = { } , { } , [ ] def update_mapping ( ex , exp , base = None ) : a = next ( generator ) symbols [ ex ] = a if base is not None : mapping [ ex ] = a ** exp + base else : mapping [ ex ] = exp . as_expr ( a ) return a def bottom_up_scan ( ex ) : if ex . is_Atom : if ex is S . ImaginaryUnit : if ex not in mapping : return update_mapping ( ex , 2 , 1 ) else : return symbols [ ex ] elif ex . is_Rational : return ex elif ex . is_Add : return Add ( * [ bottom_up_scan ( g ) for g in ex . args ] ) elif ex . is_Mul : return Mul ( * [ bottom_up_scan ( g ) for g in ex . args ] ) elif ex . is_Pow : if ex . exp . is_Rational : if ex . exp < 0 and ex . base . is_Add : coeff , terms = ex . base . as_coeff_add ( ) elt , _ = primitive_element ( terms , polys = True ) alg = ex . base - coeff # XXX: turn this into eval() inverse = invert ( elt . gen + coeff , elt ) . as_expr ( ) base = inverse . subs ( elt . gen , alg ) . expand ( ) if ex . exp == - 1 : return bottom_up_scan ( base ) else : ex = base ** ( - ex . exp ) if not ex . exp . is_Integer : base , exp = ( ex . base ** ex . exp . p ) . expand ( ) , Rational ( 1 , ex . exp . q ) else : base , exp = ex . base , ex . exp base = bottom_up_scan ( base ) expr = base ** exp if expr not in mapping : return update_mapping ( expr , 1 / exp , - base ) else : return symbols [ expr ] elif ex . is_AlgebraicNumber : if ex . root not in mapping : return update_mapping ( ex . root , ex . minpoly ) else : return symbols [ ex . root ] raise NotAlgebraic ( "%s doesn't seem to be an algebraic number" % ex ) def simpler_inverse ( ex ) : """
        Returns True if it is more likely that the minimal polynomial
        algorithm works better with the inverse
        """ if ex . is_Pow : if ( 1 / ex . exp ) . is_integer and ex . exp < 0 : if ex . base . is_Add : return True if ex . is_Mul : hit = True a = [ ] for p in ex . args : if p . is_Add : return False if p . is_Pow : if p . base . is_Add and p . exp > 0 : return False if hit : return True return False inverted = False ex = expand_multinomial ( ex ) if ex . is_AlgebraicNumber : return ex . minpoly . as_expr ( x ) elif ex . is_Rational : result = ex . q * x - ex . p else : inverted = simpler_inverse ( ex ) if inverted : ex = ex ** - 1 res = None if ex . is_Pow and ( 1 / ex . exp ) . is_Integer : n = 1 / ex . exp res = _minimal_polynomial_sq ( ex . base , n , x ) elif _is_sum_surds ( ex ) : res = _minimal_polynomial_sq ( ex , S . One , x ) if res is not None : result = res if res is None : bus = bottom_up_scan ( ex ) F = [ x - bus ] + list ( mapping . values ( ) ) G = groebner ( F , list ( symbols . values ( ) ) + [ x ] , order = 'lex' ) _ , factors = factor_list ( G [ - 1 ] ) # by construction G[-1] has root `ex` result = _choose_factor ( factors , x , ex ) if inverted : result = _invertx ( result , x ) if result . coeff ( x ** degree ( result , x ) ) < 0 : result = expand_mul ( - result ) return result