<commit_before>"""Square-free decomposition algorithms and related tools. """

from .densearith import (dmp_mul_ground, dmp_neg, dmp_quo, dmp_sub, dup_mul,
                         dup_sub)
from .densebasic import (dmp_convert, dmp_degree, dmp_ground, dmp_ground_LC,
                         dmp_inject, dmp_LC, dmp_raise, dmp_strip, dmp_zero_p)
from .densetools import (dmp_compose, dmp_diff, dmp_ground_monic,
                         dmp_ground_primitive, dup_diff, dup_monic,
                         dup_primitive, dup_shift)
from .euclidtools import (dmp_gcd, dmp_inner_gcd, dmp_resultant, dup_gcd,
                          dup_inner_gcd)
from .galoistools import gf_sqf_list, gf_sqf_part
from .polyerrors import DomainError, MultivariatePolynomialError


def dmp_sqf_p(f, u, K):
    """
    Return ``True`` if ``f`` is a square-free polynomial in ``K[X]``.

    Examples
    ========

    >>> from diofant.domains import ZZ

    >>> dmp_sqf_p([[]], 1, ZZ)
    True
    >>> dmp_sqf_p([[1], [2, 0], [1, 0, 0]], 1, ZZ)
    False
    >>> dmp_sqf_p([[1], [], [1, 0, 0]], 1, ZZ)
    True
    """
    if dmp_zero_p(f, u):
        return True
    else:
        return not dmp_degree(dmp_gcd(f, dmp_diff(f, 1, u, K), u, K), u)


def dmp_sqf_norm(f, u, K):
    """
    Square-free norm of ``f`` in ``K[X]``, useful over algebraic domains.

    Returns ``s``, ``f``, ``r``, such that ``g(x) = f(x-sa)`` and ``r(x) = Norm(g(x))``
    is a square-free polynomial over K, where ``a`` is the algebraic extension of ``K``.

    Examples
    ========

    >>> from diofant.domains import QQ
    >>> from diofant.polys import ring
    >>> from diofant.core import I

    >>> K = QQ.algebraic_field(I)
    >>> R, x, y = ring("x y", K)
    >>> _, X, Y = ring("x y", QQ)

    >>> s, f, r = R.dmp_sqf_norm(x*y + y**2)

    >>> s == 1
    True
    >>> f == x*y + y**2 + K([QQ(-1), QQ(0)])*y
    True
    >>> r == X**2*Y**2 + 2*X*Y**3 + Y**4 + Y**2
    True

    """
    if not K.is_Algebraic:
        raise DomainError("ground domain must be algebraic")

    g = dmp_raise(K.mod.rep, u + 1, 0, K.domain)
    F = dmp_raise([K.one, -K.unit], u, 0, K)

    s = 0

    while True:
        h, _ = dmp_inject(f, u, K, front=True)
        r = dmp_resultant(g, h, u + 1, K.domain)

        if dmp_sqf_p(r, u, K.domain):
            break
        else:
            f, s = dmp_compose(f, F, u, K), s + 1

    return s, f, r


def dmp_gf_sqf_part(f, u, K):
    """Compute square-free part of ``f`` in ``GF(p)[X]``. """
    if not u:
        f = dmp_convert(f, u, K, K.domain)
        g = gf_sqf_part(f, K.mod, K.domain)
        return dmp_convert(g, u, K.domain, K)
    else:  # pragma: no cover
        raise NotImplementedError('multivariate polynomials over finite fields')


def dmp_sqf_part(f, u, K):
    """
    Returns square-free part of a polynomial in ``K[X]``.

    Examples
    ========

    >>> from diofant.domains import ZZ
    >>> from diofant.polys import ring
    >>> R, x, y = ring("x y", ZZ)

    >>> R.dmp_sqf_part(x**3 + 2*x**2*y + x*y**2)
    x**2 + x*y

    """
    if K.is_FiniteField:
        return dmp_gf_sqf_part(f, u, K)

    if dmp_zero_p(f, u):
        return f

    if K.is_negative(dmp_ground_LC(f, u, K)):
        f = dmp_neg(f, u, K)

    gcd = dmp_gcd(f, dmp_diff(f, 1, u, K), u, K)
    sqf = dmp_quo(f, gcd, u, K)

    if K.has_Field:
        return dmp_ground_monic(sqf, u, K)
    else:
        return dmp_ground_primitive(sqf, u, K)[1]


def dup_gf_sqf_list(f, K, all=False):
    """Compute square-free decomposition of ``f`` in ``GF(p)[x]``. """
    f = dmp_convert(f, 0, K, K.domain)

    coeff, factors = gf_sqf_list(f, K.mod, K.domain, all=all)

    for i, (f, k) in enumerate(factors):
        factors[i] = (dmp_convert(f, 0, K.domain, K), k)

    return K.convert(coeff, K.domain), factors


def dmp_gf_sqf_list(f, u, K, all=False):
    """Compute square-free decomposition of ``f`` in ``GF(p)[X]``. """
    raise NotImplementedError('multivariate polynomials over finite fields')


def dup_sqf_list(f, K, all=False):
    """
    Return square-free decomposition of a polynomial in ``K[x]``.

    Examples
    ========

    >>> from diofant.domains import ZZ
    >>> from diofant.polys import ring

    >>> R, x = ring("x", ZZ)

    >>> f = 2*x**5 + 16*x**4 + 50*x**3 + 76*x**2 + 56*x + 16

    >>> R.dup_sqf_list(f)
    (2, [(x + 1, 2), (x + 2, 3)])
    >>> R.dup_sqf_list(f, all=True)
    (2, [(1, 1), (x + 1, 2), (x + 2, 3)])
    """
    if K.is_FiniteField:
        return dup_gf_sqf_list(f, K, all=all)

    if K.has_Field:
        coeff = dmp_LC(f, K)
        f = dup_monic(f, K)
    else:
        coeff, f = dup_primitive(f, K)

        if K.is_negative(dmp_LC(f, K)):
            f = dmp_neg(f, 0, K)
            coeff = -coeff

    if dmp_degree(f, 0) <= 0:
        return coeff, []<commit_msg>polys: drop dup_gf_sqf_list()<commit_after>"""Square-free decomposition algorithms and related tools. """

from .densearith import (dmp_mul_ground, dmp_neg, dmp_quo, dmp_sub, dup_mul,
                         dup_sub)
from .densebasic import (dmp_convert, dmp_degree, dmp_ground, dmp_ground_LC,
                         dmp_inject, dmp_LC, dmp_raise, dmp_strip, dmp_zero_p)
from .densetools import (dmp_compose, dmp_diff, dmp_ground_monic,
                         dmp_ground_primitive, dup_diff, dup_monic,
                         dup_primitive, dup_shift)
from .euclidtools import (dmp_gcd, dmp_inner_gcd, dmp_resultant, dup_gcd,
                          dup_inner_gcd)
from .galoistools import gf_sqf_list, gf_sqf_part
from .polyerrors import DomainError, MultivariatePolynomialError


def dmp_sqf_p(f, u, K):
    """
    Return ``True`` if ``f`` is a square-free polynomial in ``K[X]``.

    Examples
    ========

    >>> from diofant.domains import ZZ

    >>> dmp_sqf_p([[]], 1, ZZ)
    True
    >>> dmp_sqf_p([[1], [2, 0], [1, 0, 0]], 1, ZZ)
    False
    >>> dmp_sqf_p([[1], [], [1, 0, 0]], 1, ZZ)
    True
    """
    if dmp_zero_p(f, u):
        return True
    else:
        return not dmp_degree(dmp_gcd(f, dmp_diff(f, 1, u, K), u, K), u)


def dmp_sqf_norm(f, u, K):
    """
    Square-free norm of ``f`` in ``K[X]``, useful over algebraic domains.

    Returns ``s``, ``f``, ``r``, such that ``g(x) = f(x-sa)`` and ``r(x) = Norm(g(x))``
    is a square-free polynomial over K, where ``a`` is the algebraic extension of ``K``.

    Examples
    ========

    >>> from diofant.domains import QQ
    >>> from diofant.polys import ring
    >>> from diofant.core import I

    >>> K = QQ.algebraic_field(I)
    >>> R, x, y = ring("x y", K)
    >>> _, X, Y = ring("x y", QQ)

    >>> s, f, r = R.dmp_sqf_norm(x*y + y**2)

    >>> s == 1
    True
    >>> f == x*y + y**2 + K([QQ(-1), QQ(0)])*y
    True
    >>> r == X**2*Y**2 + 2*X*Y**3 + Y**4 + Y**2
    True

    """
    if not K.is_Algebraic:
        raise DomainError("ground domain must be algebraic")

    g = dmp_raise(K.mod.rep, u + 1, 0, K.domain)
    F = dmp_raise([K.one, -K.unit], u, 0, K)

    s = 0

    while True:
        h, _ = dmp_inject(f, u, K, front=True)
        r = dmp_resultant(g, h, u + 1, K.domain)

        if dmp_sqf_p(r, u, K.domain):
            break
        else:
            f, s = dmp_compose(f, F, u, K), s + 1

    return s, f, r


def dmp_gf_sqf_part(f, u, K):
    """Compute square-free part of ``f`` in ``GF(p)[X]``. """
    if not u:
        f = dmp_convert(f, u, K, K.domain)
        g = gf_sqf_part(f, K.mod, K.domain)
        return dmp_convert(g, u, K.domain, K)
    else:  # pragma: no cover
        raise NotImplementedError('multivariate polynomials over finite fields')


def dmp_sqf_part(f, u, K):
    """
    Returns square-free part of a polynomial in ``K[X]``.

    Examples
    ========

    >>> from diofant.domains import ZZ
    >>> from diofant.polys import ring
    >>> R, x, y = ring("x y", ZZ)

    >>> R.dmp_sqf_part(x**3 + 2*x**2*y + x*y**2)
    x**2 + x*y

    """
    if K.is_FiniteField:
        return dmp_gf_sqf_part(f, u, K)

    if dmp_zero_p(f, u):
        return f

    if K.is_negative(dmp_ground_LC(f, u, K)):
        f = dmp_neg(f, u, K)

    gcd = dmp_gcd(f, dmp_diff(f, 1, u, K), u, K)
    sqf = dmp_quo(f, gcd, u, K)

    if K.has_Field:
        return dmp_ground_monic(sqf, u, K)
    else:
        return dmp_ground_primitive(sqf, u, K)[1]


def dmp_gf_sqf_list(f, u, K, all=False):
    """Compute square-free decomposition of ``f`` in ``GF(p)[X]``. """
    if not u:
        f = dmp_convert(f, u, K, K.domain)

        coeff, factors = gf_sqf_list(f, K.mod, K.domain, all=all)

        for i, (f, k) in enumerate(factors):
            factors[i] = (dmp_convert(f, u, K.domain, K), k)

        return K.convert(coeff, K.domain), factors

    else:
        raise NotImplementedError('multivariate polynomials over finite fields')


def dup_sqf_list(f, K, all=False):
    """
    Return square-free decomposition of a polynomial in ``K[x]``.

    Examples
    ========

    >>> from diofant.domains import ZZ
    >>> from diofant.polys import ring

    >>> R, x = ring("x", ZZ)

    >>> f = 2*x**5 + 16*x**4 + 50*x**3 + 76*x**2 + 56*x + 16

    >>> R.dup_sqf_list(f)
    (2, [(x + 1, 2), (x + 2, 3)])
    >>> R.dup_sqf_list(f, all=True)
    (2, [(1, 1), (x + 1, 2), (x + 2, 3)])
    """
    if K.is_FiniteField:
        return dmp_gf_sqf_list(f, 0, K, all=all)

    if K.has_Field:
        coeff = dmp_LC(f, K)
        f = dup_monic(f, K)
    else:
        coeff, f = dup_primitive(f, K)

        if K.is_negative(dmp_LC(f, K)):
            f = dmp_neg(f, 0, K)
            coeff = -coeff

    if dmp_degree(f, 0) <= 0:
        return coeff, []
{'fraction_non_alphanumeric': 0.17161303759241903, 'fraction_numerical': 0.014474643340622722, 'mean_word_length': 2.3804998240056316, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 147, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '897443', 'n_tokens_mistral': 4126, 'n_tokens_neox': 3883, 'n_words': 1004}