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

Classes

class  Elliptic
 

Functions

def nearest_integer (x)
 
def dedekind (tau, floatpre)
 
def hilbert_mpmath (D)
 
def hilbert (D)
 
def outputHP (absbound=DEFAULT_ABS_BOUND)
 
def cmm (p)
 
def cmm_order (p)
 
def _cmm_find_disc (p, absbound=DEFAULT_ABS_BOUND)
 
def cornacchiamodify (d, p)
 
def quasi_primitive (p, disc_is_minus3)
 
def param_gen (disc, n, g)
 
def _generate_params_for_minus3 (n, g)
 
def _generate_params_for_minus4 (n, g)
 
def _generate_params_for_general_disc (disc, n, g)
 
def ecpp (n, era=None)
 
def _ecpp_find_disc (n, era=None)
 
def _factor_order (m, u, era=None)
 
def next_disc (d, absbound)
 
def disc_gen (absbound=DEFAULT_ABS_BOUND)
 

Variables

 log = mpmath.log
 
 _log = logging.getLogger('nzmath.ecpp')
 
list default_orders
 
dictionary orders
 
int DEFAULT_ABS_BOUND = 200000
 

Function Documentation

◆ _cmm_find_disc()

def nzmath.ecpp._cmm_find_disc (   p,
  absbound = DEFAULT_ABS_BOUND 
)
private
Input : a prime number p (>=3)
Output : (disc, g, u, v) where:
        - disc: discriminant appropriate for CM method
        - g: quasi primitive element of p
        - u, v: a solution of u**2 + disc * v**2 = 4*p

Definition at line 270 of file ecpp.py.

References nzmath.ecpp.cornacchiamodify(), nzmath.ecpp.disc_gen(), and nzmath.ecpp.quasi_primitive().

Referenced by nzmath.ecpp.cmm(), and nzmath.ecpp.cmm_order().

◆ _ecpp_find_disc()

def nzmath.ecpp._ecpp_find_disc (   n,
  era = None 
)
private
Return (disc, m, k, q, era) where:
- disc: appropriate discriminant for ecpp
- m: one of possible orders for disc
- k: smooth part of m
- q: rough part of m which is greater than (n^(1/4) + 1)^2
- era: list of small primes

Definition at line 444 of file ecpp.py.

References nzmath.ecpp._factor_order(), nzmath.ecpp.cornacchiamodify(), and nzmath.ecpp.disc_gen().

Referenced by nzmath.ecpp.ecpp().

◆ _factor_order()

def nzmath.ecpp._factor_order (   m,
  u,
  era = None 
)
private
Return triple (k, q, primes) if m is factored as m = kq,
where k > 1 and q is a probable prime > u.
u is expected to be (n^(1/4)+1)^2 for Atkin-Morain ECPP.
If m is not successfully factored into desired form,
return (False, False, primes).
The third component of both cases is a list of primes
to do trial division.

Algorithm 27 (Atkin-morain ECPP) Step3

Definition at line 473 of file ecpp.py.

References nzmath.ecpp.log.

Referenced by nzmath.ecpp._ecpp_find_disc().

◆ _generate_params_for_general_disc()

def nzmath.ecpp._generate_params_for_general_disc (   disc,
  n,
  g 
)
private
Generate curve params for discriminant other than -3 or -4.

Definition at line 390 of file ecpp.py.

References nzmath.ecpp.hilbert().

Referenced by nzmath.ecpp.param_gen().

◆ _generate_params_for_minus3()

def nzmath.ecpp._generate_params_for_minus3 (   n,
  g 
)
private
Generate curve params for discriminant -3.

Definition at line 370 of file ecpp.py.

References nzmath.bigrange.range().

Referenced by nzmath.ecpp.param_gen().

◆ _generate_params_for_minus4()

def nzmath.ecpp._generate_params_for_minus4 (   n,
  g 
)
private
Generate curve params for discriminant -4.

Definition at line 380 of file ecpp.py.

References nzmath.bigrange.range().

Referenced by nzmath.ecpp.param_gen().

◆ cmm()

def nzmath.ecpp.cmm (   p)
Algorithm 25 (CM methods)
Input : a prime number p (>=3)
Output : curve parameters for CM curves

Definition at line 241 of file ecpp.py.

References nzmath.ecpp._cmm_find_disc(), and nzmath.ecpp.param_gen().

◆ cmm_order()

def nzmath.ecpp.cmm_order (   p)
Algorithm 25 (CM methods)
Input : a prime number p (>=3)
Output : curve parameters for CM curves and orders

Definition at line 250 of file ecpp.py.

References nzmath.ecpp._cmm_find_disc(), and nzmath.ecpp.param_gen().

◆ cornacchiamodify()

def nzmath.ecpp.cornacchiamodify (   d,
  p 
)
Algorithm 26 (Modified cornacchia)
Input : p be a prime and d be an integer such that d < 0 and d > -4p with
        d = 0, 1 (mod 4)
Output : the solution of u^2 -d * v^2 = 4p.

Definition at line 288 of file ecpp.py.

Referenced by nzmath.ecpp._cmm_find_disc(), and nzmath.ecpp._ecpp_find_disc().

◆ dedekind()

def nzmath.ecpp.dedekind (   tau,
  floatpre 
)
Algorithm 22 (Dedekind eta)
Input : tau in the upper half-plane, k in N
Output : eta(tau)

Definition at line 54 of file ecpp.py.

References nzmath.ecpp.nearest_integer().

Referenced by nzmath.ecpp.hilbert_mpmath().

◆ disc_gen()

def nzmath.ecpp.disc_gen (   absbound = DEFAULT_ABS_BOUND)
Generate negative discriminants.

The order of discriminants depends on how to produce them.
By default, discriminants are in ascending order of class
numbers while reading from precomputed data file, then
in descending order of discriminant itself.

If discriminant reach the absbound, then StopIteration will be
raised.  The default value of absbound is DEFAULT_ABS_BOUND.

Definition at line 518 of file ecpp.py.

References nzmath.ecpp.next_disc().

Referenced by nzmath.ecpp._cmm_find_disc(), nzmath.ecpp._ecpp_find_disc(), and nzmath.ecpp.outputHP().

◆ ecpp()

def nzmath.ecpp.ecpp (   n,
  era = None 
)
Algorithm 27 (Atkin-Morain ECPP)
Input : a natural number n
Output : If n is prime, retrun True. Else, return False

Definition at line 403 of file ecpp.py.

References nzmath.ecpp._ecpp_find_disc(), nzmath.ecpp.param_gen(), and nzmath.ecpp.quasi_primitive().

◆ hilbert()

def nzmath.ecpp.hilbert (   D)
wrapper to split mpmath part and others.

Definition at line 133 of file ecpp.py.

References nzmath.ecpp.hilbert_mpmath().

Referenced by nzmath.ecpp._generate_params_for_general_disc(), and nzmath.ecpp.outputHP().

◆ hilbert_mpmath()

def nzmath.ecpp.hilbert_mpmath (   D)
Algorithm 23&24 (Floating-point precision & Hilbert class polynomial)
Input : a negative fundamental discriminant D
Output : the class number h(D) and the Hilbert class polynomial T in Z[X]

Definition at line 89 of file ecpp.py.

References nzmath.ecpp.dedekind(), nzmath.ecpp.nearest_integer(), and nzmath.bigrange.range().

Referenced by nzmath.ecpp.hilbert().

◆ nearest_integer()

def nzmath.ecpp.nearest_integer (   x)
Round x to nearest integer.

Definition at line 22 of file ecpp.py.

Referenced by nzmath.ecpp.dedekind(), and nzmath.ecpp.hilbert_mpmath().

◆ next_disc()

def nzmath.ecpp.next_disc (   d,
  absbound 
)
Return fundamental discriminant D, such that D < d.
If there is no D with |d| < |D| < absbound, return False

Definition at line 501 of file ecpp.py.

Referenced by nzmath.ecpp.disc_gen().

◆ outputHP()

def nzmath.ecpp.outputHP (   absbound = DEFAULT_ABS_BOUND)
Output Hilbert class polynomials to file 'Hilbert_Poly.txt'.

Definition at line 156 of file ecpp.py.

References nzmath.ecpp.disc_gen(), and nzmath.ecpp.hilbert().

◆ param_gen()

def nzmath.ecpp.param_gen (   disc,
  n,
  g 
)

◆ quasi_primitive()

def nzmath.ecpp.quasi_primitive (   p,
  disc_is_minus3 
)
Return g s.t.
0) 1 < g < p
1) quadratic nonresidue modulo p
and
2) cubic nonresidue modulo p if p == 1 mod 3
with p >= 3, a prime.

For p, not a prime, condition 1 means the Jacobi symbol
(g/p) != -1, and condition 2 means g doesn't have order
dividing (p - 1)//3.

if disc_is_minus3 is True, cubic nonresidue check becomes
stricter so that g**((p-1)//3) must match with one of the
primitive third roots of unity.

Definition at line 323 of file ecpp.py.

Referenced by nzmath.ecpp._cmm_find_disc(), and nzmath.ecpp.ecpp().

Variable Documentation

◆ _log

nzmath.ecpp._log = logging.getLogger('nzmath.ecpp')
private

Definition at line 40 of file ecpp.py.

◆ DEFAULT_ABS_BOUND

int nzmath.ecpp.DEFAULT_ABS_BOUND = 200000

Definition at line 52 of file ecpp.py.

◆ default_orders

list nzmath.ecpp.default_orders
Initial value:
1 = [lambda n, u, v: n + 1 + u,
2  lambda n, u, v: n + 1 - u]

Definition at line 43 of file ecpp.py.

◆ log

nzmath.ecpp.log = mpmath.log

Definition at line 20 of file ecpp.py.

Referenced by nzmath.imaginary.Complex.__pow__(), and nzmath.ecpp._factor_order().

◆ orders

dictionary nzmath.ecpp.orders
Initial value:
1 = {-3: default_orders + [lambda n, u, v: n + 1 - ((u + 3*v) >> 1),
2  lambda n, u, v: n + 1 + ((u + 3*v) >> 1),
3  lambda n, u, v: n + 1 - ((u - 3*v) >> 1),
4  lambda n, u, v: n + 1 + ((u - 3*v) >> 1)],
5  -4: default_orders + [lambda n, u, v: n + 1 + (v << 1),
6  lambda n, u, v: n + 1 - (v << 1)]}

Definition at line 45 of file ecpp.py.