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).