NZMATH  1.2.0
About: NZMATH is a Python based number theory oriented calculation system.
  Fossies Dox: NZMATH-1.2.0.tar.gz  ("inofficial" and yet experimental doxygen-generated source code documentation)  

nzmath.poly.factor Namespace Reference


def zassenhaus (f)
def padic_factorization (f)
def brute_force_search (f, fp_factors, q)
def padic_lift_list (f, factors, p, q)
def extgcdp (f, g, p)
def minimum_absolute_injection (f)
def upper_bound_of_coefficient (f)
def find_combination (f, d, factors, q)
def divisibility_test (f, g)
def integerpolynomialfactorization (f)

Function Documentation

◆ brute_force_search()

def nzmath.poly.factor.brute_force_search (   f,
brute_force_search(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.

Definition at line 81 of file

References nzmath.poly.factor.find_combination().

Referenced by nzmath.poly.factor.zassenhaus().

◆ divisibility_test()

def nzmath.poly.factor.divisibility_test (   f,
Return boolean value whether f is divisible by g or not, for polynomials.

Definition at line 236 of file

Referenced by nzmath.poly.factor.find_combination().

◆ extgcdp()

def nzmath.poly.factor.extgcdp (   f,
extgcdp(f,g,p) -> u,v,w

Find u,v,w such that f*u + g*v = w = gcd(f,g) mod p.

Definition at line 138 of file

References nzmath.poly.factor.minimum_absolute_injection().

Referenced by nzmath.poly.factor.padic_lift_list().

◆ find_combination()

def nzmath.poly.factor.find_combination (   f,
find_combination(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,[]).

Definition at line 209 of file

References nzmath.poly.factor.divisibility_test(), and nzmath.poly.factor.minimum_absolute_injection().

Referenced by nzmath.poly.factor.brute_force_search().

◆ integerpolynomialfactorization()

def nzmath.poly.factor.integerpolynomialfactorization (   f)
integerpolynomialfactorization -> list of (factors,index) of f.

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

Definition at line 248 of file

References nzmath.poly.factor.zassenhaus().

◆ minimum_absolute_injection()

def nzmath.poly.factor.minimum_absolute_injection (   f)
minimum_absolute_injection(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.

Definition at line 161 of file

Referenced by nzmath.poly.factor.extgcdp(), nzmath.poly.factor.find_combination(), nzmath.poly.factor.padic_factorization(), and nzmath.poly.factor.padic_lift_list().

◆ padic_factorization()

def nzmath.poly.factor.padic_factorization (   f)
padic_factorization(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.

Definition at line 44 of file

References nzmath.gcd.gcd(), and nzmath.poly.factor.minimum_absolute_injection().

Referenced by nzmath.poly.factor.zassenhaus().

◆ padic_lift_list()

def nzmath.poly.factor.padic_lift_list (   f,
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.

Definition at line 104 of file

References nzmath.poly.factor.extgcdp(), and nzmath.poly.factor.minimum_absolute_injection().

◆ upper_bound_of_coefficient()

def nzmath.poly.factor.upper_bound_of_coefficient (   f)
upper_bound_of_coefficient(polynomial) -> int

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.

Definition at line 186 of file

References nzmath.bigrange.range().

Referenced by nzmath.poly.factor.zassenhaus().

◆ zassenhaus()

def nzmath.poly.factor.zassenhaus (   f)
zassenhaus(f) -> list of factors of f.

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

Definition at line 12 of file

References nzmath.poly.factor.brute_force_search(), nzmath.arith1.inverse(), nzmath.poly.factor.padic_factorization(), and nzmath.poly.factor.upper_bound_of_coefficient().

Referenced by nzmath.poly.factor.integerpolynomialfactorization().