UserManual

zassenhaus

The zassenhaus module is for factorizations of integer coefficient one variable polynomials. It is based on a van Hoeij's paper.

Functions

bruteForceSearch(f, fp_factors, q)

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.

combinationIndexGenerator(n, m)

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)

complexRootAbsoluteUpperBound(f) -> m

Return an upper bound of absolute value of complex root of given (complex coefficient) polynomial f.

divisibilityTest(f, g)

Return boolean value whether f is divisible by g or not, for polynomials.

extgcdp(f, g, p)

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)

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)

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.

newMatrix(s, d)

create a random s by d matrix.

padicFactorization(f)

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.

padicLiftList(f, factors, p, q)

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.

tri(f)

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(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)

vanHoeij(f) -> list of factors of f.

Factor a squarefree monic integer coefficient polynomial f with van Hoeij's knapsack method.

zassenhaus(f)

zassenhaus(f) -> list of factors of f.

Factor a squarefree monic integer coefficient polynomial f with Berlekamp-Zassenhaus method.


Last-modified: 2005-12-18 (Æü) 17:51:34