The zassenhaus module is for factorizations of integer coefficient one variable polynomials. It is based on a van Hoeij's paper.
bruteForceSearch(f, fp_factors, q) -> [factors]
Find the factorization of f by searching a factor which is a product of some combination in fp_factors. The combination is searched by brute force.
Generate indeces of m elment subsets of n element set.
For example:
>>> for idx in combinationIndexGenerator(5,3): ... print idx ... [0, 1, 2] [0, 1, 3] [0, 1, 4] [0, 2, 3] [0, 2, 4] [0, 3, 4] [1, 2, 3] [1, 2, 4] [1, 3, 4] [2, 3, 4] >>>
(moved to combinatorial.py in 0.5.0)
complexRootAbsoluteUpperBound(f) -> m
Return an upper bound of absolute value of complex root of given (complex coefficient) polynomial f.
Return boolean value whether f is divisible by g or not, for polynomials.
extgcdp(f,g,p) -> u,v,w
Find u,v,w such that f*u + g*v = w = gcd(f,g) mod p.
findCombination(f, d, factors, q) -> g, list
Find a combination of d factors which divides f (or its complement). The returned values are: the product g of the combination and a list consisting of the combination itself. If there is no combination, return (0,[]).
minimumAbsoluteInjection(f) -> F
Return an integer coefficient polynomial F by injection of a Z/pZ coefficient polynomial f with sending each coefficient to minimum absolute representatives.
create a random s by d matrix.
padicFactorization(f) -> p, factors
Return a prime p and a p-adic factorization of given integer coefficient squarefree polynomial f. The result factors have integer coefficients, injected from F_p to its minimum absolute representation. The prime is chosen to be:
1) f is still squarefree mod p, 2) the number of factors is not greater than with the successive prime.
padicLift(f, factors, p, q) -> lifted_factors
Find a lifted integer coefficient polynomials such that:
'''f''' = G1*G2*...*Gm (mod '''q'''*'''p'''), Gi = gi (mod '''q'''),
from f and gi's of integer coefficient polynomials such that:
'''f''' = g1*g2*...*gm (mod '''q'''), gi's are pairwise coprime
with positive integers p dividing q.
tr(f) -> list of Tr_i(f)
Return the list of Tr_i(f) for a monic integer coefficient polynomial f in range 0 < i <= deg(f). Tr_i(f) is defined as the sum of i-th powered roots of f.
upperBoundOfCoefficient(polynomial) -> long
Compute Landau-Mignotte bound of coefficients of factors, whose degree is no greater than half of the given polynomial. The given polynomial must have integer coefficients.
vanHoeij(f) -> list of factors of f.
Factor a squarefree monic integer coefficient polynomial f with van Hoeij's knapsack method.
zassenhaus(f) -> list of factors of f.
Factor a squarefree monic integer coefficient polynomial f with Berlekamp-Zassenhaus method.