CPG - Class Polynomial Generator

Overview
Examples of use
Modular equations
Changes

Overview

CPG is, as its name says, a generator of class polynomials. When this is possible, it also generates data allowing to build the factors over the genus field of the class polynomials (see Factoring Class Polynomials over the Genus Field).

CPG can work with 45 class invariants (they are associated with modular equations Phi[p](X, J)=0 of degree at most 11 on J).

The current alpha version has some limitations:

Discriminant -D such that -67108864 < -D < -4
Class number h(-D) ≤ 1920
Genus number g(-D) ≤ 64

Executable for use under Win XP on 32-bit processors

Examples of use

Class polynomial H(x) with real coefficients

D=10707
gcd(D,3)=3
(D mod 8)=3
Invariant=w(43,4)
ClassNumber=12
GenusNumber=4

Class polynomial H(x)
---------------------
Degree=12
H[12]=1
H[11]=96255480793427752200850
H[10]=5864874876897440085145369138535
H[9]=9833170036265698951668989612850
H[8]=62984656638430167666877068487718635
H[7]=-231983864643816930151840918148079700
H[6]=201728710473087907453984249289242779802
H[5]=-428938165726417503850753857655799365300
H[4]=215332007100121695649686988622880957056635
H[3]=62159037721783979299238387817834805579650
H[2]=68549832164247789904802368641464405226454535
H[1]=2080223620723835597492067643701389411650
H[0]=39959630797262576401

Max(|H[i]|) = |H[2]| (binary size = 146)
Binary precision used = 256

Factorization of H(x) over the genus field
------------------------------------------
Degree=3
G=4
F=[-3,-43,-83]
A[0]=1
A[1]=129
A[2]=249
A[3]=3569
S[0]=(+ + + +)
S[1]=(+ - + -)
S[2]=(+ + - -)
S[3]=(+ - - +)
M[0,0]=52104048811571732877106700
M[1,0]=4587505699938287468007120
M[2,0]=3301959928240388489941680
M[3,0]=872164083441042546807744
M[0,1]=429184477595092415175110
M[1,1]=37787586227948850529040
M[2,1]=27198461140069037570960
M[3,1]=7184072928430813118550
M[0,2]=96255480793427752200850
M[1,2]=8474822530338214020320
M[2,2]=6099943242468820369280
M[3,2]=1611210166909961209410

Max(|M[i,j]|) = |M[0,0]| (binary size = 86)
Binary precision used = 160

Checks
------
|H[0]| = 43^12
Computing a random pseudoprime P such that 4P = U^2 + 10707 V^2
P = 31573
U = 173
Computing Q(x), product over Z/P of the factors obtained over the genus field
Q(x) = H(x) mod P
Computing j-invariant
J = 28216
The curve y^2 = x^3 + 16397 x + 17350 has (P + 1 - U) points over Z/P

Running times
-------------
Computing roots            : 0.01s
Building polynomial        : 0.00s
Computing genus field data : 0.00s
Checks                     : 0.00s

Class polynomial H(x) with complex coefficients

D=10707
gcd(D,3)=3
(D mod 8)=3
Invariant=w(19,2)
ClassNumber=12
GenusNumber=4
                           1 + Sqrt(-10707)
Working over Z[w] with w = ----------------
                                  2
"(a,b)" stands for "a + bw"

Class polynomial H(x)
---------------------
Degree=12
H[12]=(1,0)
H[11]=(101974746444,1830729308)
H[10]=(390373809693900,11663907218922)
H[9]=(13158098980177612,-5047004183016)
H[8]=(30002386396053177,-2000834061257519)
H[7]=(-663174676485994936,-4135138548373352)
H[6]=(-1813935775451547264,64625604667427232)
H[5]=(10343793869802709896,158961488406136832)
H[4]=(25464547444744026595,-570805738613547562)
H[3]=(-48104808034063448852,-1466951223736236084)
H[2]=(-94083300950662701612,19381350676289694)
H[1]=(-335973763942430164,-1559108129113688)
H[0]=(-25860797,-754767)

Max = |H[2].a| (binary size = 67)
Binary precision used = 192

Factorization of H(x) over the genus field
------------------------------------------
Degree=3
G=4
F=[-3,-43,-83]
A[0]=1
A[1]=1/129
A[2]=1/249
A[3]=1/3569
S[0]=(+ + + +)
S[1]=(+ - + -)
S[2]=(+ + - -)
S[3]=(+ - - +)
M[0,0]=(-1828341300828,21090006132)
M[1,0]=(20765965344488,-239536423672)
M[2,0]=(28850742465048,-332794722312)
M[3,0]=(-109227148111536,1259940483984)
M[0,1]=(-93976652660,-13228194016)
M[1,1]=(1067369594288,150243402800)
M[2,1]=(1482928117872,208737376320)
M[3,1]=(-5614275245312,-790266952232)
M[0,2]=(101974746444,1830729308)
M[1,2]=(-1158210477176,-20793087896)
M[2,2]=(-1609134199560,-28888420440)
M[3,2]=(6092083755808,109369794616)

Max(|M[i,j]|) = |M[3,0].a| (binary size = 47)
Binary precision used = 128

Checks
------
Norm(H[0]) = 19^12
Computing a random prime P such that 4P = U^2 + 10707 V^2
P = 38371
U = 239
Computing Q(x), product over Z/P of the factors obtained over the genus field
Q(x) = H(x) mod P
Computing j-invariant
J = 15777
The curve y^2 = x^3 + 13095 x + 24317 has (P + 1 - U) points over Z/P

Running times
-------------
Computing roots            : 0.00s
Building polynomial        : 0.00s
Computing genus field data : 0.00s
Checks                     : 0.00s

Modular equations

Except with Hilbert polynomials, a modular equation is necessary to get the j-invariant of an elliptic curve from a root of a class polynomial. The Phi[p](X, J)'s used by CPG and having a degree on J greater than 1 were computed with the program mueller.exe written by Michael Scott.
The following files contain lists of integers (representing the Phi[p](X, J)'s) that can be read with

  Read(p)

  repeat

    Read(coefficient)

    Read(degree_on_X)

    Read(degree_on_J)

  until (degree_on_X = 0) and (degree_on_J = 0)

Other modular equations (up to Phi[997]) can be found at
ftp://ftp.informatik.tu-darmstadt.de/pub/TI/systems/LiDIA/MOD_EQ/

Changes

v2.0.3 (alpha)

Added 6 new class invariants.

v2.0.1 (alpha)

Polynomial degrees up to 1920 (instead of 1280).