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