Inheritance diagram for nzmath.poly.hensel.HenselLiftSimultaneously:

Collaboration diagram for nzmath.poly.hensel.HenselLiftSimultaneously:

Public Member Functions
def	__init__ (self, target, factors, cofactors, bases, p)

def	from_factors (cls, target, factors, p, ubound=sys.maxint)

def	first_lift (self)

def	general_lift (self)

def	lift (self)

Public Attributes
	f

	gis

	his

	r

	sis

	tis

	p

	dis

	q

	bis

	uis

	yis

	zis

	modp

Properties
	factors = property(_get_factors)

Private Member Functions
def	_init_dis (self)

def	_solve_yz (self, i)

def	_get_factors (self)

def	_assertEqualModulo (self, expected, actual, modulus, message=None)

Detailed Description

INVARIANTS:
  ai's, pi's and gi's are monic
  f == g1*g2*...*gr (mod p)
  f == d0 + d1*p + d2*p**2 +...+ dk*p**k
  hi == g(i+1)*...*gr
  1 == gi*si + hi*ti (mod p) (i = 1, 2,..., r)
  deg(si) < deg(hi), deg(ti) < deg(gi)
  p | q
  f == l1*l2*...*lr (mod q/p)
  f == a1*a2*...*ar (mod q)
  ui == ai*yi + bi*zi (mod p) (i = 1, 2,..., r)

REFERENCE:
G.E.Collins & M.J.Encarnaci'on.
Improved Techniques for factoring Univariate Polynomials,
J.Symb.Comp. 21, 313--327 (1996).

Definition at line 277 of file hensel.py.

Constructor & Destructor Documentation

◆ init()

def nzmath.poly.hensel.HenselLiftSimultaneously.__init__	(	self,
		target,
		factors,
		cofactors,
		bases,
		p
	)

Prepare attributes

Definition at line 297 of file hensel.py.

Member Function Documentation

◆ _assertEqualModulo()

def nzmath.poly.hensel.HenselLiftSimultaneously._assertEqualModulo	(	self,
		expected,
		actual,
		modulus,
		message = `None`
	)

private

assert expected == actual (mod modulus)

Definition at line 481 of file hensel.py.

Referenced by nzmath.poly.hensel.HenselLiftSimultaneously._solve_yz(), nzmath.poly.hensel.HenselLiftSimultaneously.first_lift(), and nzmath.poly.hensel.HenselLiftSimultaneously.general_lift().

◆ _get_factors()

def nzmath.poly.hensel.HenselLiftSimultaneously._get_factors ( self )

private

getter for factors of target mod q

Definition at line 470 of file hensel.py.

References nzmath.poly.hensel.HenselLiftSimultaneously.gis.

◆ _init_dis()

def nzmath.poly.hensel.HenselLiftSimultaneously._init_dis ( self )

private

Return p-adic expansion of target polynomial.

This method is private for __init__.

Definition at line 321 of file hensel.py.

References nzmath.poly.hensel.HenselLiftSimultaneously.dis, nzmath.poly.hensel.HenselLiftPair.f, nzmath.ecpp.Elliptic.f, nzmath.poly.hensel.HenselLiftMulti.f, nzmath.poly.hensel.HenselLiftSimultaneously.f, nzmath.poly.hensel.HenselLiftSimultaneously.modp, nzmath.poly.hensel.HenselLiftPair.p, nzmath.poly.hensel.HenselLiftMulti.p, and nzmath.poly.hensel.HenselLiftSimultaneously.p.

Referenced by nzmath.poly.hensel.HenselLiftSimultaneously.first_lift().

◆ _solve_yz()

def nzmath.poly.hensel.HenselLiftSimultaneously._solve_yz	(	self,
		i
	)

private

Solve the equation
    gi Y + hi Z = ui (mod p)
satisfying conditions:
(1) deg(Y) < deg(hi) and
(2) deg(Z) < deg(gi),
and return a tuple(Y, Z).
The method needs the following conditions:
(I) deg(ui) <= deg(gi)deg(hi),
(II)  gi si + hi ti = 1 (mod p).

Definition at line 447 of file hensel.py.

References nzmath.poly.hensel.HenselLiftSimultaneously._assertEqualModulo(), nzmath.poly.hensel.HenselLiftSimultaneously.gis, nzmath.poly.hensel.HenselLiftSimultaneously.his, nzmath.poly.hensel.HenselLiftSimultaneously.modp, nzmath.poly.hensel.HenselLiftPair.p, nzmath.poly.hensel.HenselLiftMulti.p, nzmath.poly.hensel.HenselLiftSimultaneously.p, nzmath.poly.hensel.HenselLiftSimultaneously.sis, nzmath.poly.hensel.HenselLiftSimultaneously.tis, and nzmath.poly.hensel.HenselLiftSimultaneously.uis.

Referenced by nzmath.poly.hensel.HenselLiftSimultaneously.first_lift(), and nzmath.poly.hensel.HenselLiftSimultaneously.general_lift().

◆ first_lift()

def nzmath.poly.hensel.HenselLiftSimultaneously.first_lift ( self )

Start lifting.
    f == l1*l2*...*lr (mod p**2)
Initialize di's, ui's, yi's and zi's.
Update ai's, bi's.
Then, update q with p**2.

Definition at line 359 of file hensel.py.

◆ from_factors()

def nzmath.poly.hensel.HenselLiftSimultaneously.from_factors	(	cls,
		target,
		factors,
		p,
		ubound = `sys.maxint`
	)

Create and return an instance of HenselLiftSimultaneously,
whose factors are lifted by HenselLiftMulti upto ubound (if it
is smaller than sys.maxint, or upto sys.maxint).

HenselLiftSimultaneously.from_factors(f, factors, p)

The parameters satisfy that:
  f == a1*...*ar (mod p)
with a prime number p and ai's in factors.

Definition at line 338 of file hensel.py.

◆ general_lift()

def nzmath.poly.hensel.HenselLiftSimultaneously.general_lift ( self )

Continue lifting.
    f == a1*a2*...*ar (mod p*q)
Update ai's, bi's, ui's, yi's and zi's.
Then, update q with p*q.

Definition at line 401 of file hensel.py.

Referenced by nzmath.poly.hensel.HenselLiftSimultaneously.lift().

◆ lift()

def nzmath.poly.hensel.HenselLiftSimultaneously.lift ( self )

The lift

Definition at line 441 of file hensel.py.

References nzmath.poly.hensel.HenselLiftSimultaneously.general_lift().

Member Data Documentation

◆ bis

nzmath.poly.hensel.HenselLiftSimultaneously.bis

Definition at line 315 of file hensel.py.

Referenced by nzmath.poly.hensel.HenselLiftSimultaneously.first_lift(), and nzmath.poly.hensel.HenselLiftSimultaneously.general_lift().

◆ dis

nzmath.poly.hensel.HenselLiftSimultaneously.dis

Definition at line 309 of file hensel.py.

Referenced by nzmath.poly.hensel.HenselLiftSimultaneously._init_dis(), nzmath.poly.hensel.HenselLiftSimultaneously.first_lift(), and nzmath.poly.hensel.HenselLiftSimultaneously.general_lift().

◆ f

nzmath.poly.hensel.HenselLiftSimultaneously.f

Definition at line 302 of file hensel.py.

Referenced by nzmath.poly.hensel.HenselLiftSimultaneously._init_dis(), nzmath.poly.hensel.HenselLiftSimultaneously.first_lift(), and nzmath.poly.hensel.HenselLiftSimultaneously.general_lift().

◆ gis

nzmath.poly.hensel.HenselLiftSimultaneously.gis

Definition at line 303 of file hensel.py.

Referenced by nzmath.poly.hensel.HenselLiftSimultaneously._get_factors(), nzmath.poly.hensel.HenselLiftSimultaneously._solve_yz(), nzmath.poly.hensel.HenselLiftSimultaneously.first_lift(), and nzmath.poly.hensel.HenselLiftSimultaneously.general_lift().

◆ his

nzmath.poly.hensel.HenselLiftSimultaneously.his

Definition at line 304 of file hensel.py.

Referenced by nzmath.poly.hensel.HenselLiftSimultaneously._solve_yz(), and nzmath.poly.hensel.HenselLiftSimultaneously.first_lift().

◆ modp

nzmath.poly.hensel.HenselLiftSimultaneously.modp

Definition at line 319 of file hensel.py.

Referenced by nzmath.poly.hensel.HenselLiftSimultaneously._init_dis(), and nzmath.poly.hensel.HenselLiftSimultaneously._solve_yz().

◆ p

nzmath.poly.hensel.HenselLiftSimultaneously.p

Definition at line 308 of file hensel.py.

Referenced by nzmath.poly.hensel.HenselLiftSimultaneously._init_dis(), nzmath.poly.hensel.HenselLiftSimultaneously._solve_yz(), nzmath.poly.hensel.HenselLiftSimultaneously.first_lift(), and nzmath.poly.hensel.HenselLiftSimultaneously.general_lift().

◆ q

nzmath.poly.hensel.HenselLiftSimultaneously.q

Definition at line 312 of file hensel.py.

Referenced by nzmath.poly.hensel.HenselLiftSimultaneously.first_lift(), and nzmath.poly.hensel.HenselLiftSimultaneously.general_lift().

◆ r

nzmath.poly.hensel.HenselLiftSimultaneously.r

Definition at line 305 of file hensel.py.

Referenced by nzmath.poly.hensel.HenselLiftSimultaneously.first_lift(), and nzmath.poly.hensel.HenselLiftSimultaneously.general_lift().

◆ sis

nzmath.poly.hensel.HenselLiftSimultaneously.sis

Definition at line 306 of file hensel.py.

Referenced by nzmath.poly.hensel.HenselLiftSimultaneously._solve_yz().

◆ tis

nzmath.poly.hensel.HenselLiftSimultaneously.tis

Definition at line 307 of file hensel.py.

Referenced by nzmath.poly.hensel.HenselLiftSimultaneously._solve_yz().

◆ uis

nzmath.poly.hensel.HenselLiftSimultaneously.uis

Definition at line 316 of file hensel.py.

Referenced by nzmath.poly.hensel.HenselLiftSimultaneously._solve_yz(), nzmath.poly.hensel.HenselLiftSimultaneously.first_lift(), and nzmath.poly.hensel.HenselLiftSimultaneously.general_lift().

◆ yis

nzmath.poly.hensel.HenselLiftSimultaneously.yis

Definition at line 316 of file hensel.py.

Referenced by nzmath.poly.hensel.HenselLiftSimultaneously.first_lift(), and nzmath.poly.hensel.HenselLiftSimultaneously.general_lift().

◆ zis

nzmath.poly.hensel.HenselLiftSimultaneously.zis

Definition at line 316 of file hensel.py.

Referenced by nzmath.poly.hensel.HenselLiftSimultaneously.first_lift(), and nzmath.poly.hensel.HenselLiftSimultaneously.general_lift().

Property Documentation

◆ factors

nzmath.poly.hensel.HenselLiftSimultaneously.factors = property(_get_factors)

static

Definition at line 479 of file hensel.py.

Referenced by nzmath.prime.FactoredInteger.__iter__(), nzmath.prime.FactoredInteger.__mod__(), nzmath.prime.FactoredInteger.__mul__(), nzmath.prime.FactoredInteger.__pow__(), nzmath.prime.FactoredInteger.copy(), nzmath.prime.FactoredInteger.divisors(), nzmath.prime.FactoredInteger.exact_division(), nzmath.prime.FactoredInteger.is_divisible_by(), and nzmath.prime.FactoredInteger.prime_divisors().

The documentation for this class was generated from the following file:

nzmath/poly/hensel.py

Public Member Functions

Public Attributes

Properties

Private Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ __init__()

Member Function Documentation

◆ _assertEqualModulo()

◆ _get_factors()

◆ _init_dis()

◆ _solve_yz()

◆ first_lift()

◆ from_factors()

◆ general_lift()

◆ lift()

Member Data Documentation

◆ bis

◆ dis

◆ f

◆ gis

◆ his

◆ modp

◆ p

◆ q

◆ r

◆ sis

◆ tis

◆ uis

◆ yis

◆ zis

Property Documentation

◆ factors

◆ init()