These are chat archives for symengine/symengine

23rd
Jul 2016
Brent Lewis
@coder0xff
Jul 23 2016 17:57
What is the motivation for the Add class having a coef_ field?
Isuru Fernando
@isuruf
Jul 23 2016 18:07
@coder0xff, so that numerical values are combined together. 1 + x + 1 is combined into 2 + x
Otherwise you have to search the entire dictionary for a numerical value
Nishant Nikhil
@nishnik
Jul 23 2016 22:00
from sympy import *
from sympy.polys.galoistools import *
from math import ceil as _ceil, sqrt as _sqrt

def gf_edf_zassenhaus2(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 range(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)
            try:
               g = gf_gcd(f, gf_sub_ground(h, K.one, p, K), p, K)
            except:
               continue


        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 factors
@isuruf try running this on any input
you will also have to add
```
def _gf_pow_pnm1d2(f, n, g, b, p, K):
    """
    utility function for ``gf_edf_zassenhaus``
    Compute ``f**((p**n - 1) // 2)`` in ``GF(p)[x]/(g)``
    ``f**((p**n - 1) // 2) = (f*f**p*...*f**(p**n - 1))**((p - 1) // 2)``
    """
    f = gf_rem(f, g, p, K)
    h = f
    r = f
    for i in range(1, n):
        h = gf_frobenius_map(h, g, b, p, K)
        r = gf_mul(r, h, p, K)
        r = gf_rem(r, g, p, K)

    res = gf_pow_mod(r, (p - 1)//2, g, p, K)
    return res
Isuru Fernando
@isuruf
Jul 23 2016 22:08
Will it always find a factor? I'm asking this because an exception is better than an infinite recursion
Nishant Nikhil
@nishnik
Jul 23 2016 22:10
I think yes! but I will read a little more and confirm
Isuru Fernando
@isuruf
Jul 23 2016 22:10
Great
Nishant Nikhil
@nishnik
Jul 23 2016 22:11
I will revert the current commit and then can we merge the PR for now ?
Isuru Fernando
@isuruf
Jul 23 2016 22:11
Yes
Nishant Nikhil
@nishnik
Jul 23 2016 22:11
ok