Source code for diofant.polys.sqfreetools

"""Square-free decomposition algorithms and related tools. """

from .densearith import dmp_mul, dmp_quo, dmp_sub
from .densebasic import (dmp_degree_in, dmp_ground_LC, dmp_ground_p,
                         dmp_inject, dmp_one_p, dmp_raise, dmp_swap,
                         dmp_zero_p)
from .densetools import (dmp_compose, dmp_diff_in, dmp_ground_monic,
                         dmp_ground_primitive)
from .euclidtools import dmp_gcd, dmp_resultant
from .polyerrors import DomainError


[docs]def dmp_sqf_p(f, u, K): """ Return ``True`` if ``f`` is a square-free polynomial in ``K[X]``. Examples ======== >>> R, x, y = ring("x y", ZZ) >>> R.dmp_sqf_p(R(0)) True >>> R.dmp_sqf_p((x + y)**2) False >>> R.dmp_sqf_p(x**2 + y**2) True """ if dmp_ground_p(f, None, u): return True else: g = f for i in range(u + 1): g = dmp_gcd(g, dmp_diff_in(f, 1, i, u, K), u, K) if dmp_ground_p(g, None, u): return True return False
[docs]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 ======== >>> K = QQ.algebraic_field(I) >>> R, x, y = ring("x y", K) >>> R.dmp_sqf_norm(x*y + y**2) (1, x*y - I*x + y**2 - 3*I*y - 2, x**2*y**2 + x**2 + 2*x*y**3 + 2*x*y + y**4 + 5*y**2 + 4) """ if not K.is_AlgebraicField: raise DomainError("ground domain must be algebraic") g = dmp_raise(K.mod.to_dense(), 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): return s, f, r else: for j in range(u + 1): f = dmp_swap(f, 0, j, u, K) f = dmp_compose(f, F, u, K) f = dmp_swap(f, 0, j, u, K) s += 1
[docs]def dmp_sqf_part(f, u, K): """ Returns square-free part of a polynomial in ``K[X]``. Examples ======== >>> 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: _, sqf = dmp_sqf_list(f, u, K) g = [K.one] for f, _ in sqf: g = dmp_mul(g, f, u, K) return g if dmp_zero_p(f, u): return f gcd = f for i in range(u + 1): gcd = dmp_gcd(gcd, dmp_diff_in(f, 1, i, u, K), u, K) sqf = dmp_quo(f, gcd, u, K) if K.is_Field: return dmp_ground_monic(sqf, u, K) else: return dmp_ground_primitive(sqf, u, K)[1]
[docs]def dmp_gf_sqf_list(f, u, K): """Compute square-free decomposition of ``f`` in ``GF(p)[X]``. Returns the leading coefficient of ``f`` and a square-free decomposition ``f_1**e_1 f_2**e_2 ... f_k**e_k`` such that all ``f_i`` are monic polynomials and ``(f_i, f_j)`` for ``i != j`` are co-prime. Examples ======== >>> R, x = ring('x', FF(11)) >>> f = x**11 + 1 Note that: >>> f.diff() 0 mod 11 This phenomenon doesn't happen in characteristic zero. However we can still compute square-free decomposition of ``f``: >>> R.dmp_sqf_list(f) (1 mod 11, [(x + 1 mod 11, 11)]) References ========== * :cite:`Geddes1992algorithms` """ if u: raise NotImplementedError('multivariate polynomials over finite fields') n, sqf, factors, r = 1, False, [], int(K.characteristic) lc, f = dmp_ground_primitive(f, 0, K) if dmp_degree_in(f, 0, 0) < 1: return lc, [] while True: F = dmp_diff_in(f, 1, 0, 0, K) if F != []: g = dmp_gcd(f, F, 0, K) h = dmp_quo(f, g, 0, K) i = 1 while h != [K.one]: G = dmp_gcd(g, h, 0, K) H = dmp_quo(h, G, 0, K) if dmp_degree_in(H, 0, 0) > 0: factors.append((H, i*n)) g, h, i = dmp_quo(g, G, 0, K), G, i + 1 if g == [K.one]: sqf = True else: f = g if not sqf: d = dmp_degree_in(f, 0, 0) // r for i in range(d + 1): f[i] = f[i*r] f, n = f[:d + 1], n*r else: break return lc, factors
[docs]def dmp_rr_yun0_sqf_list(f, u, K): """Compute square-free decomposition of ``f`` in zero-characteristic ring ``K``. References ========== * :cite:`LeeM2013factor`, page 8 """ if dmp_ground_p(f, None, u): return [] result, count = [], 1 qs = [dmp_diff_in(f, 1, i, u, K) for i in range(u + 1)] g = f for q in qs: g = dmp_gcd(g, q, u, K) while not dmp_one_p(f, u, K): for i in range(u + 1): qs[i] = dmp_quo(qs[i], g, u, K) f = dmp_quo(f, g, u, K) for i in range(u + 1): qs[i] = dmp_sub(qs[i], dmp_diff_in(f, 1, i, u, K), u, K) g = f for q in qs: g = dmp_gcd(g, q, u, K) if not dmp_one_p(g, u, K): result.append((g, count)) count += 1 return result
[docs]def dmp_sqf_list(f, u, K): """ Return square-free decomposition of a polynomial in ``K[X]``. Examples ======== >>> R, x, y = ring("x y", ZZ) >>> R.dmp_sqf_list(x**5 + 2*x**4*y + x**3*y**2) (1, [(x + y, 2), (x, 3)]) """ if K.is_Field: coeff = dmp_ground_LC(f, u, K) f = dmp_ground_monic(f, u, K) else: coeff, f = dmp_ground_primitive(f, u, K) if K.is_FiniteField: return coeff, dmp_gf_sqf_list(f, u, K)[1] return coeff, dmp_rr_yun0_sqf_list(f, u, K)