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.quad Namespace Reference

Classes

class  ClassGroup
 
class  ReducedQuadraticForm
 
class  ReducedQuadraticFormForBSGS
 
class  RetNext
 following functions are sub functions for above functions. More...
 

Functions

def class_formula (disc, uprbd)
 
def class_number (disc, limit_of_disc=100000000)
 
def class_group (disc, limit_of_disc=100000000)
 
def class_number_bsgs (disc)
 
def class_group_bsgs (disc, classnum, qin)
 
def disc (f)
 
def reducePDF (f)
 
def sqrPDF (f)
 
def powPDF (f, exp, ut=None)
 
def compositePDF (f_1, f_2)
 
def unit_form (disc)
 
def kronecker (a, b)
 
def number_unit (disc)
 
def crt (inlist)
 
def rand_generator (disc, classnum, qin)
 
def sqroot (disc, p)
 
def randomele (disc, unit)
 
def isfundamental (disc)
 
def euclid_exd (a, b)
 
def parteucl (a, b, sogsp)
 
def isfinished_bsgscv (n, sossp, sogsp, nt, lpt, qpt, disc, classnum, indofg)
 
def ordercv (n, sossp, sogsp, nt, disc, classnum, tmp_ss, tmp_gs)
 
def giantspcv (q, sz, y, c_s1, bounds, sogsp)
 
def babyspcv (bounds, sossp, sogsp, utwi, nt, disc, classnum)
 
def trbabysp (q, x, bounds, sossp, sogsp, ut, h, nt, disc)
 
def trgiantsp (stride_index, pivot, stride, c_s1, bounds, sogsp)
 
def trorder (n, sossp, sogsp, nt, disc)
 
def isfinished_trbsgs (lwrbd, bounds, h, n, sossp, sogsp, nt, disc)
 
def _update_subgrps (q, element, sossp, sogsp, discriminant)
 
def setind (n, indofg, tmp_ss, tmp_gs)
 

Function Documentation

◆ _update_subgrps()

def nzmath.quad._update_subgrps (   q,
  element,
  sossp,
  sogsp,
  discriminant 
)
private
update sossp and sogsp

Definition at line 1118 of file quad.py.

References nzmath.bigrange.range().

Referenced by nzmath.quad.isfinished_trbsgs().

◆ babyspcv()

def nzmath.quad.babyspcv (   bounds,
  sossp,
  sogsp,
  utwi,
  nt,
  disc,
  classnum 
)
Compute small steps

Definition at line 965 of file quad.py.

References nzmath.quad.giantspcv(), nzmath.quad.ordercv(), and nzmath.bigrange.range().

Referenced by nzmath.quad.class_group_bsgs().

◆ class_formula()

def nzmath.quad.class_formula (   disc,
  uprbd 
)
Return the approximation of class number 'h' with the given discriminant.
h = sqrt(|D|)/pi (1 - (D/p)(1/p))^{-1} where p is less than ubound.

Definition at line 186 of file quad.py.

References nzmath.quad.kronecker(), and nzmath.quad.number_unit().

Referenced by nzmath.quad.class_number_bsgs().

◆ class_group()

def nzmath.quad.class_group (   disc,
  limit_of_disc = 100000000 
)
Return the class number and the class group with the given discriminant
by counting reduced forms. Not only fundamental discriminant.

Definition at line 229 of file quad.py.

◆ class_group_bsgs()

def nzmath.quad.class_group_bsgs (   disc,
  classnum,
  qin 
)
Return the construction of the class group with the given discriminant.

Definition at line 343 of file quad.py.

References nzmath.quad.babyspcv(), nzmath.quad.isfinished_bsgscv(), nzmath.quad.rand_generator(), nzmath.quad.setind(), and nzmath.quad.unit_form().

◆ class_number()

def nzmath.quad.class_number (   disc,
  limit_of_disc = 100000000 
)
Return class number with the given discriminant by counting reduced forms.
Not only fundamental discriminant.

Definition at line 198 of file quad.py.

◆ class_number_bsgs()

def nzmath.quad.class_number_bsgs (   disc)
Return the class number with the given discriminant.

Definition at line 290 of file quad.py.

References nzmath.quad.class_formula(), nzmath.quad.isfinished_trbsgs(), nzmath.quad.trbabysp(), and nzmath.quad.trorder().

◆ compositePDF()

def nzmath.quad.compositePDF (   f_1,
  f_2 
)
Return the reduced form of composition of the given forms 'f_1' and 'f_2'.
'f_1' and 'f_2' are quadratic forms with same disc.

Definition at line 583 of file quad.py.

References nzmath.quad.disc(), nzmath.quad.euclid_exd(), and nzmath.quad.reducePDF().

Referenced by nzmath.quad.ReducedQuadraticForm.__mul__(), nzmath.quad.ReducedQuadraticForm.__truediv__(), and nzmath.quad.powPDF().

◆ crt()

def nzmath.quad.crt (   inlist)
Chinese Remainder Theorem, Algo. 1.3.11 of Cohen's Book.

Definition at line 693 of file quad.py.

References nzmath.bigrange.range().

Referenced by nzmath.quad.sqroot().

◆ disc()

def nzmath.quad.disc (   f)
Return the discriminant of the given quadratic form 'f'.
f = [a, b, c]

Definition at line 463 of file quad.py.

Referenced by nzmath.quad.compositePDF(), nzmath.quad.powPDF(), and nzmath.quad.sqrPDF().

◆ euclid_exd()

def nzmath.quad.euclid_exd (   a,
  b 
)
Return a tuple (u, v, d); they are the greatest common divisor d
of two integers a and b and u, v such that d = a * u + b * v.

Definition at line 801 of file quad.py.

Referenced by nzmath.quad.compositePDF(), and nzmath.quad.sqrPDF().

◆ giantspcv()

def nzmath.quad.giantspcv (   q,
  sz,
  y,
  c_s1,
  bounds,
  sogsp 
)
giant step called from babyspcv.

q: int
sz, y: element

Definition at line 942 of file quad.py.

Referenced by nzmath.quad.babyspcv().

◆ isfinished_bsgscv()

def nzmath.quad.isfinished_bsgscv (   n,
  sossp,
  sogsp,
  nt,
  lpt,
  qpt,
  disc,
  classnum,
  indofg 
)
Determine whether the bsgs algorithm is finished or not yet.
This is a submodule called by the bsgs module.

Definition at line 856 of file quad.py.

References nzmath.bigrange.range().

Referenced by nzmath.quad.class_group_bsgs().

◆ isfinished_trbsgs()

def nzmath.quad.isfinished_trbsgs (   lwrbd,
  bounds,
  h,
  n,
  sossp,
  sogsp,
  nt,
  disc 
)
Determine whether bsgs is finished or not yet.
This is a submodule called by the bsgs module.

lwrbd, h, n: int
nt: element

Definition at line 1094 of file quad.py.

References nzmath.quad._update_subgrps().

Referenced by nzmath.quad.class_number_bsgs().

◆ isfundamental()

def nzmath.quad.isfundamental (   disc)
Determine whether the given discriminant is fundamental or not.

Definition at line 784 of file quad.py.

◆ kronecker()

def nzmath.quad.kronecker (   a,
  b 
)
Compute the Kronecker symbol (a/b) using algo 1.4.10 in Cohen's book.

Definition at line 643 of file quad.py.

Referenced by nzmath.quad.RetNext._randomele1(), and nzmath.quad.class_formula().

◆ number_unit()

def nzmath.quad.number_unit (   disc)
Return the number of units with the given discriminant.

Definition at line 680 of file quad.py.

Referenced by nzmath.quad.class_formula().

◆ ordercv()

def nzmath.quad.ordercv (   n,
  sossp,
  sogsp,
  nt,
  disc,
  classnum,
  tmp_ss,
  tmp_gs 
)
n: int

Definition at line 913 of file quad.py.

Referenced by nzmath.quad.babyspcv().

◆ parteucl()

def nzmath.quad.parteucl (   a,
  b,
  sogsp 
)
Do extended partial Euclidean algorithm on 'a' and 'b'.

Definition at line 829 of file quad.py.

Referenced by nzmath.quad.sqrPDF().

◆ powPDF()

def nzmath.quad.powPDF (   f,
  exp,
  ut = None 
)
Return the powering 'exp' of the given quadratic form 'f'.

Definition at line 552 of file quad.py.

References nzmath.quad.compositePDF(), nzmath.quad.disc(), nzmath.quad.sqrPDF(), and nzmath.quad.unit_form().

Referenced by nzmath.quad.ReducedQuadraticForm.__pow__().

◆ rand_generator()

def nzmath.quad.rand_generator (   disc,
  classnum,
  qin 
)
Return the reduced random quadratic form with given discriminant and order t,
where t = classnum / a ** b and qin = [a, b].

Definition at line 722 of file quad.py.

References nzmath.quad.randomele(), and nzmath.quad.unit_form().

Referenced by nzmath.quad.class_group_bsgs().

◆ randomele()

def nzmath.quad.randomele (   disc,
  unit 
)
Return a reduced random form with the given discriminant and the given unit.
Also random element is not unit.

Definition at line 760 of file quad.py.

References nzmath.quad.reducePDF().

Referenced by nzmath.quad.rand_generator().

◆ reducePDF()

def nzmath.quad.reducePDF (   f)
Return the reduced form of the given positive definite form 'f'.
f = (f_1, f_2, f_3)

Definition at line 475 of file quad.py.

Referenced by nzmath.quad.compositePDF(), nzmath.quad.ReducedQuadraticForm.inverse(), nzmath.quad.randomele(), nzmath.quad.sqroot(), and nzmath.quad.sqrPDF().

◆ setind()

def nzmath.quad.setind (   n,
  indofg,
  tmp_ss,
  tmp_gs 
)
 

Definition at line 1145 of file quad.py.

References nzmath.bigrange.range().

Referenced by nzmath.quad.class_group_bsgs().

◆ sqroot()

def nzmath.quad.sqroot (   disc,
  p 
)
Return a reduced quadratic form with the given discriminant.
'disc' is a quadratic residue mod 'p'.

Definition at line 736 of file quad.py.

References nzmath.quad.crt(), and nzmath.quad.reducePDF().

Referenced by nzmath.quad.RetNext._randomele1().

◆ sqrPDF()

def nzmath.quad.sqrPDF (   f)
Return the square of the given quadratic form 'f'.

Definition at line 510 of file quad.py.

References nzmath.quad.disc(), nzmath.quad.euclid_exd(), nzmath.quad.parteucl(), and nzmath.quad.reducePDF().

Referenced by nzmath.quad.powPDF().

◆ trbabysp()

def nzmath.quad.trbabysp (   q,
  x,
  bounds,
  sossp,
  sogsp,
  ut,
  h,
  nt,
  disc 
)
Compute small steps.

q, h: int
ut: unit element
nt: element

Definition at line 1012 of file quad.py.

References nzmath.bigrange.range(), nzmath.quad.trgiantsp(), and nzmath.quad.trorder().

Referenced by nzmath.quad.class_number_bsgs().

◆ trgiantsp()

def nzmath.quad.trgiantsp (   stride_index,
  pivot,
  stride,
  c_s1,
  bounds,
  sogsp 
)
Compute giant steps.

stride_index: int
pivot, stride: element

Definition at line 1046 of file quad.py.

Referenced by nzmath.quad.trbabysp().

◆ trorder()

def nzmath.quad.trorder (   n,
  sossp,
  sogsp,
  nt,
  disc 
)
Compute the order.

n: int
nt: element

Definition at line 1065 of file quad.py.

Referenced by nzmath.quad.class_number_bsgs(), and nzmath.quad.trbabysp().

◆ unit_form()

def nzmath.quad.unit_form (   disc)
Return generated quadratic form with the given discriminant.

Definition at line 627 of file quad.py.

Referenced by nzmath.quad.class_group_bsgs(), nzmath.quad.powPDF(), and nzmath.quad.rand_generator().