Good. I am glad the thing is moving. 10^26? You need 10^13*4,and 2,3,5,7
give at best 210=2*10^2(are you using fullSchoof for Atkin primes?) so
your babygiant is doing 2*10^11 or 500,000 in both sorted and matching lists?
(maybe less root(2) using +/-.) Note on the unmodified babygiant one should
start near c=0 according to the distribution formula. (BY "modified"BG I
mean using some data of my type c=list mod q.)
Terminology.
Elkies primes (frobenius has roots in GF(q))
Atkin primes (.........................(q^2))
Type 1 modular equations : F=q^s.eta... and j PHI
2 A and j,where A(tau)=A(-1/(q*tau)). PSI
I have renotated both my essays to reflect this. In my first essay,
f=1/F.
Genus zero is,in the long run,too special to bother about. Better
have generic programs. ESPECIALLY when distributed,& your critical time
is going to be that of your biggest q.
My CHARLA does in fact follow their CCR paper,but later I realised
that the ending described in my 2nd essay is better(but not worth
changing,since time is small oh of other times for given q). You should
arrange one checking place,since(doing it my way with A)this is sometimes
the only may of killing "bad" j(q*tau).
In your case,the modular equations probably should be stored. I
could arrange to send them all(though I dont store myself),if we agreed
on the format and list of Chinese primes used.
Once you have the degree (q-1)/2 equation for X,how to find the
eigenvalue? First,how good is your adding of points on elliptic curves
over GF(p^k),where p is say 100-digit and k is around 75? Mine is slow,
since I get inverses by a non-Lehmerized polynomial Euclid. But all my
X^P and Y^P is fast,relatively. The two ways are:
get (X,Y),2(X,Y),3(X,Y),...... and match with (X^P,Y^P). Average
number of adds is q/4. In real life one should ONLY match Y^P,+/-,
and leave proof via X^P till later(perhaps you could do X and Y
simultaneously,but then you need a submachine),during the babygiant,
maybe. or:
Do a baby giant sort and match here: this needs both X^P and
Y^P calculated,but for large q it might pay.
I know it pays to use the Atkin primes,but they are much more
programming,both at each relevant q,and in the cunning sort-and-match.
Also,they need a LOT of storage to do efficiently.
I am not clear from what you say whether you have the PSI(A,j)=0
working on q=23? I.e.,not just getting the equation,but the complete
deduction of E4q E6q (from first differentiations) and then E2* from
second diferentiation?
I am sending you GETPAA,which finds the DA,DJ,DAA,etc,but note we
do NOT this time use DA/A,but DA is the honest partial,for PSI equations,
and the GETALL which gets the needed E4Q,etc. However this time there
is a CHARLA inside GETALL,since we may need to try many possible
j(q*tau),and we only exit when we get that check in CHARLA. Also
a(partly) updated second essay. oa
SUBROUTINE GETPAA(AVAL,JVAL,DA,DJ,DAA,DAJ,DJJ,P,Q,ORD,VALEN,CUF)
IMPLICIT INTEGER(A-Z)
DIMENSION AVAL(9),JVAL(9),DA(9),DJ(9),DAA(9),DAJ(9),DJJ(9),P(9)
DIMENSION LOC(2),LOC2(2),CUF(9)
COMMON/ZLWORK/W(1000)
COMMON/ZLSAFE/SAFE
C (CUF IS" P(1)+1,Q+1,2*V+1"TRIPLE ARRAY.... CUF(1,L,R) IS THE COEFFICIENT
C OF J**(R-1) * A**(Q+1-L) IN THE MODULAR EQUATION A**(Q+1)+SIGMA CUF(1,L,R)*
C THESE =0. L FROM 1 TO Q+1,AND R FROM 1 TO (CORRECT A FORM)
C ORD=1 FIRST PARTIALS ONLY: ORD=2 SEOND(5 VALUES)
V=2*VALEN
C SET UP CONSTANTS FOR TRIPLE ARRAY CUF
K2=P(1)+1
K3=K2*(Q+1)
K1=1-K2-K3
S=SAFE
S2=S+P(1)+1
SAFE=S2+P(1)+1
LOC(1)=1
LOC2(1)=1
LOC2(2)=1
DA(1)=1
DA(2)=Q+1
DO1L=1,Q
REND=(VALEN*(Q-1+L))/Q+1
CALL ZLMMUL(LOC2,CUF(K1+K2*L+K3*REND),W(S),P)
DO2R=REND-1,1,-1
2 CALL ZLMMAD(CUF(K1+K2*L+K3*R),W(S),JVAL,W(S),P)
LOC(2)=Q+1-L
CALL ZLMMUL(LOC,W(S),W(S),P)
1 CALL ZLMMAD(W(S),DA,AVAL,DA,P)
C CALL ZLMMUL(DA,AVAL,DA,P)
C NOTE IN CONTRAST TO GETPAR WE USE A' NOT A'/A*A
********** DA COMPUTED ***********
DJ(1)=1
DJ(2)=0
DO3L=1,Q+1
REND=(VALEN*(Q-1+L))/Q+1
IF(REND.EQ.1)GOTO3
LOC(2)=REND-1
CALL ZLMMUL(CUF(K1+K2*L+K3*REND),LOC,W(S),P)
DO4R=REND-1,2,-1
LOC(2)=R-1
CALL ZLMMUL(CUF(K1+K2*L+K3*R),LOC,W(S2),P)
4 CALL ZLMMAD(W(S2),JVAL,W(S),W(S),P)
CALL ZLMMAD(W(S),DJ,AVAL,DJ,P)
3 CONTINUE
CALL ZLMMUL(DJ,JVAL,DJ,P)
C****** DJ COMPUTED ******************************
IF(ORD.EQ.1)GOTO77777
DAA(1)=1
DAA(2)=(Q+1)*Q
DO11L=1,Q-1
REND=(VALEN*(Q-1+L))/Q+1
CALL ZLMMUL(LOC2,CUF(K1+K2*L+K3*REND),W(S),P)
DO12R=REND-1,1,-1
12 CALL ZLMMAD(CUF(K1+K2*L+K3*R),W(S),JVAL,W(S),P)
LOC(2)=(Q+1-L)*(Q-L)
CALL ZLMMUL(LOC,W(S),W(S2),P)
11 CALL ZLMMAD(W(S2),DAA,AVAL,DAA,P)
C CALL ZLMMUL(DAA,AVAL,DAA,P)
********** DAA COMPUTED ***********
DJJ(1)=1
DJJ(2)=0
DO13L=1,Q+1
REND=(VALEN*(Q-1+L))/Q+1
IF(REND.EQ.1)GOTO13
LOC(2)=(REND-1)*(REND-1)
CALL ZLMMUL(CUF(K1+K2*L+K3*REND),LOC,W(S),P)
DO14R=REND-1,2,-1
LOC(2)=(R-1)*(R-1)
CALL ZLMMUL(CUF(K1+K2*L+K3*R),LOC,W(S2),P)
14 CALL ZLMMAD(W(S2),JVAL,W(S),W(S),P)
CALL ZLMMAD(W(S),DJJ,AVAL,DJJ,P)
13 CONTINUE
CALL ZLMMUL(DJJ,JVAL,DJJ,P)
C****** DJJ COMPUTED ******************************
DAJ(1)=1
DAJ(2)=0
DO21L=1,Q
REND=(VALEN*(Q-1+L))/Q+1
IF(REND.LT.2)GOTO21
LOC(2)=REND-1
CALL ZLMMUL(LOC,CUF(K1+K2*L+K3*REND),W(S),P)
DO22R=REND-1,2,-1
LOC(2)=R-1
CALL ZLMMUL(LOC,CUF(K1+K2*L+K3*R),W(S2),P)
22 CALL ZLMMAD(W(S2),W(S),JVAL,W(S),P)
LOC(2)=Q+1-L
CALL ZLMMUL(LOC,W(S),W(S),P)
CALL ZLMMAD(W(S),DAJ,AVAL,DAJ,P)
21 CONTINUE
CALL ZLMMUL(DAJ,JVAL,DAJ,P)
C CALL ZLMMUL(DAJ,AVAL,DAJ,P)
C******************** END OF COMPUTATION OF DAJ
77777 SAFE=S
RETURN
END
SUBROUTINE GETALL(AVAL,JVAL,A,B,E2Q,AQ,BQ,P,Q,FLAG,VALEN,ELKCOF
+,CUF)
C GIVEN ELLIPTIC CURVE Y2=X3+AX+B MODULO P AND JVAL DEDUCED AND AVAL FOUND
C WE GET E2Q AQ AND BQ READY FOR USE IN CHARLA.
IMPLICIT INTEGER(A-Z)
DIMENSION A(9),B(9),AQ(9),BQ(9),E2Q(9),AVAL(9),JVAL(9),P(9)
DIMENSION ELKCOF(9),CUF(9)
COMMON/PRINT/NPRINT
COMMON/ZLWORK/W(10000)
COMMON/ZLSAFE/SAFE
DIMENSION E4(25),E6(25),E4Q(25),E6Q(25),LOC(25),LOC2(25),LOC3(25)
DIMENSION LOC4(25),E6BY4(25),DELTA(25),E6BY4Q(25)
DIMENSION DAA(25),DJJ(25),DAJ(25),DA(25),DJ(25)
DIMENSION QAA(25),QJJ(25),QAJ(25),QA(25),QJ(25)
DIMENSION JQ(25),DELTAQ(25),APRIME(25),NEWJVL(1000)
FLAG=0
LOC(1)=1
LOC(2)=3
CALL ZLMDIV(A,LOC,E4,P)
IF(E4(2).NE.0)CALL ZLDIF(P,E4,E4)
LOC(2)=2
CALL ZLMDIV(B,LOC,E6,P)
IF(E6(2).NE.0)CALL ZLDIF(P,E6,E6)
CALL GETPAA(AVAL,JVAL,DA,DJ,DAA,DAJ,DJJ,P,Q,2,VALEN,CUF)
CALL ZLMDIV(E6,E4,E6BY4,P)
CALL ZLMMUL(DJ,E6BY4,LOC2,P)
CALL ZLMDIV(LOC2,DA,APRIME,P)
C***** APRIME SHOULD HAVE PLAIN A'(TAU)
CALL GETJQN(NEWJVL,DEG,AVAL,JVAL,Q,P,VALEN,CUF)
IF(DEG.LE.0)THEN
FLAG=-1
GOTO77777
ENDIF
C****** MAJOR LOOP TRYING ALL POSSIBLE VALUES OF J(QT)*************
DO666TIMES=1,DEG
CALL BLVNOC(NEWJVL(1+(TIMES-1)*P(1)),JQ,1,P)
IF(ZLMAX(JVAL, JQ ).EQ.0)THEN
PRINT*,' GOOD CHECK OF OWN NEW J = ORIGINAL J'
GOTO666
ENDIF
CALL GETPAA(AVAL,JQ,QA,QJ,QAA,QAJ,QJJ,P,Q,2,VALEN,CUF)
LOC(1)=1
LOC(2)=Q
CALL ZLMMUL(APRIME,QA,LOC2,P)
CALL ZLMMUL(LOC,QJ,LOC3,P)
CALL ZLMDIV(LOC2,LOC3,LOC3,P)
C***** LOC3 CONTAINS E6Q/E4Q***
LOC(2)=1728
CALL ZLMSUB(JQ,LOC,LOC2,P)
CALL ZLMDIV(JQ,LOC2,LOC2,P)
CALL ZLMSQU(LOC3,LOC4,P)
CALL ZLMMUL(LOC2,LOC4,E4Q,P)
CALL ZLMMUL(E4Q,LOC3,E6Q,P)
C***** FOR NOW TO PRINT AQ,BQ
LOC(2)=3
CALL ZLMMUL(LOC,E4Q,AQ,P)
IF(AQ(2).NE.0)CALL ZLDIF(P,AQ,AQ)
LOC(2)=2
CALL ZLMMUL(LOC,E6Q,BQ,P)
IF(BQ(2).NE.0)CALL ZLDIF(P,BQ,BQ)
LOC(2)=Q**2
CALL ZLMSQU(LOC,LOC2,P)
CALL ZLMMUL(AQ,LOC2,AQ,P)
CALL ZLMMUL(LOC,LOC2,LOC2,P)
CALL ZLMMUL(BQ,LOC2,BQ,P)
C WE NOW USE A''/A'=1/3.E6/E4-1/2.E4**2/E6 +E2/6 +1/DA(-DJJ*(E6/E4)**2 /A'
C+2*DAJ*E6/E4-DAA*A')
CALL ZLMMUL(E6BY4,DAJ,LOC2,P)
CALL ZLMADD(LOC2,LOC2,LOC2,P)
CALL ZLMMSB(LOC2,DAA,APRIME,LOC2,P)
CALL ZLMSQU(E6BY4,LOC3,P)
CALL ZLMDIV(LOC3,APRIME,LOC3,P)
CALL ZLMMSB(LOC2,LOC3,DJJ,LOC2,P)
CALL ZLMDIV(LOC2,DA,LOC2,P)
LOC(2)=3
CALL ZLMDIV(E6BY4,LOC,LOC3,P)
CALL ZLMADD(LOC3,LOC2,LOC2,P)
CALL ZLMADD(E6BY4,E6BY4,LOC3,P)
CALL ZLMDIV(E4,LOC3,LOC3,P)
CALL ZLMSUB(LOC2,LOC3,LOC2,P)
C****** LOC2 HAS A''/A'-E2/6. ***NOW DO ALL AT OTHER CUSP.
LOC(2)=Q
CALL ZLMDIV(E6Q,E4Q,E6BY4Q,P)
CALL ZLMMUL(E6BY4Q,LOC,E6BY4Q,P)
LOC(2)=Q*Q
CALL ZLMMUL(E4Q,LOC,E4Q,P)
C**** NORMALISE BY Q PER DIFFERENTIATION.
CALL ZLMMUL(E6BY4Q,QAJ,LOC4,P)
CALL ZLMADD(LOC4,LOC4,LOC4,P)
CALL ZLMMSB(LOC4,QAA,APRIME,LOC4,P)
CALL ZLMSQU(E6BY4Q,LOC3,P)
CALL ZLMDIV(LOC3,APRIME,LOC3,P)
CALL ZLMMSB(LOC4,LOC3,QJJ,LOC4,P)
CALL ZLMDIV(LOC4,QA,LOC4,P)
LOC(2)=3
CALL ZLMDIV(E6BY4Q,LOC,LOC3,P)
CALL ZLMADD(LOC3,LOC4,LOC4,P)
CALL ZLMADD(E6BY4Q,E6BY4Q,LOC3,P)
CALL ZLMDIV(E4Q,LOC3,LOC3,P)
CALL ZLMSUB(LOC4,LOC3,LOC4,P)
C LOC4 HAS A''/A'-Q*E2(QT)/6
CALL ZLMSUB(LOC2,LOC4,LOC2,P)
LOC(2)=3*Q
CALL ZLMMUL(LOC,LOC2,E2Q,P)
C E2Q HAS NORMALISED E2* BEGINNINING Q*(Q-1)/2+....
C PRINT*,' FINALLY TRY E2Q'
C CALL ZLPR10(E2Q)
SVPRNT=NPRINT
IF(NPRINT.GT.0)NPRINT=0
CALL CHARLA(E2Q,A,B,AQ,BQ,ELKCOF,Q,P,FLAG)
NPRINT=SVPRNT
IF(FLAG.EQ.0)GOTO77777
666 CONTINUE
FLAG=-1
77777 CONTINUE
RETURN
END
*****This is FLLPTS FSSAY as of 16 Sep 1992******
((SENT OUT ON NMBRTHRY Network: 22 ii 92)
Let P+1-c be the number of points on the elliptic curve y**2=x**3+A*x+B modulo
some(large)prime P. I recently circulated some data for P of up to 75 decimal
digits,computed with Volker Mueller. These may well prove to be the swan song
of a vanishing era,since the powerful new idea of Elkies has transformed the
subject. At this point I should state some sources.
(S)Schoof,R.,Elliptic Curves over Finite Fields,Math. Comp.44(1985),483.
(A)Atkin,A.O.L.,The Number of Points on an Elliptic Curve Modulo a Prime ,
(1988-1991),available on request via e-mail.
(CCR)Charlap,L.S.,Coley,R.,Robbins,D.P.,Enumeration of Rational Points on
Elliptic Curves over Finite Fields,Draft.
(E)Elkies,N.,Explicit Isogenies,Preprint.
Of these,I have not actually seen a copy of (E),but its existence
is asserted by (CCR),who characterize their own paper as a "variant of Elkies'
improvement of the Schoof algorithm". Their perspicuous exposition,together
with their elegant algorithm in Sections 4 and 5,enabled me to grasp the
essential beauty and simplicity of Elkies's idea. Apart from that,however,
once I have been given an address in Modular City I prefer to use my own
transportation.
Since there is now considerable variety in the mathematics and
programming involved in the problem,it is to be hoped that more people will
try their hand at it. Good amateurs using commercial algebra should be able to
break 100 digits in P without too much difficulty,and competent professionals
will no doubt aim at 150. On the other hand,200 digits would probably require
an effort on the scale needed for the ascent of F9,and it is hard to conceive
any particular elliptic curve and prime with the charisma needed to justify it.
I hope to write out a practical account within the next two weeks,and
will send this via e-mail on request. In the meantime,I offer below the number
of points on the curve y**2=x**3+ 105*x +78153 modulo (10**99 +289),namely:
10000 00000 00000 00000 00000 00000 00000 00000 00000 00000
36030 65754 17632 27655 12810 31247 46765 27865 76807 47844 .
I computed this in two ways. Firstly,it seemed fitting that Elkies's
new idea alone*should break 100 digits,and using only the primes q=
5,11,13,19,23,29,37,61,71,89,97,107,109,113,157,167,173,179,193,197,199,
211,223,227,239,263,269;
for all of which ((c**2-4*P)/q)=1 or 0,and whose product is 1.8 * 10**52,
the value of c was obtained uniquely modulo q for each q,and hence(since
its absolute value is less than 5.7 * 10**49)uniquely.
Next,using the "hard" Chinese information of the above list for
q from 5 to 167 inclusive,together with q=7 and q=163(where (A) gives the
unique value zero modulo q),and q=8,9,17,for which Volker Mueller sent me
the results of Schoof's algorithm,I obtained c uniquely to a modulus of size
6.0 * 10**32. For the primes ("soft" Chinese information)
q=43,53,79,83,101,127,131,137,149,
whose product is 5.1* 10**17,the methods of (A) showed that c is congruent to
one of 6.5 * 10**8 possible values. Now a sort-and-match program yielded again
the exact value of c.
It is obvious that the "mixed" method is more effective,enabling one
to stop at q=167 rather than q=269. I do not yet have a polished canonical
program,and so cannot state precisely the time advantage of the mixed method,
but it is considerable(a factor of between 3 and 10).
As (CCR) point out in Section 5,their method encounters a difficulty when
applied to large finite fields of small characteristic(especially the
cryptographically interesting case of P=2**m). I do not know what is said in
(E) on this point. The techniques of (S) and (A) are substantially unaffected.
A final remark is that the writers of computer algebra systems do not
really need any of these advanced techniques. For any P up to 20 decimal digits
a sort-and-match using baby-giant steps is extremely fast and easy to write,and
probably all that most users will ever need.
***************************************************************
*(For all I know,someone has already done 100 decimal digits; but I have
not heard of it. The main point is that it was clearly unattainable using only
(S) and (A),and that (E) makes it not merely possible,but quite easy.)
*********************************end of NMBRTHRY note **************
The "practical account" promised above now follows belatedly in a first
very rough draft. Since 22 ii 92 I have done 120 and 130 decimal digits,
and expect to do 150 soon in about 20 CPU hours on the IBM.
***************************************************************
9. Frobenius,Elliptic Curves over GF(p**d),and Eigenvalues
*******************************************************
Given our elliptic curve y**2 = x**3 + A*x + B defined over GF(p),
we now consider the entire q X q group G of q-division points defined over
various extensions GF(p**d),with d minimal in every case. Frobenius acts
as (x,y) to (x**p,y**p) on this,and maps G into itself,and can thus be
regarded as a 2-by-2 matrix with respect to some basis of G. If the trace
of this matrix is c,then the eigenvalues are the roots of k**2 -c.k + p=0
(mod q),and we distinguish three cases.
Case 1. The roots k1 and k2 are distinct in GF(q). In this case there are basis
elements G1 and G2 of G such that G1\Tp = k1.G1 and G2\Tp = k2.G2. The
(q-1) nonzero multiples of G1 also have eigenvalue k1,and ditto G2,k2.
If d1,d2,are the orders of k1,k2, in GF(q),then the points which are
multiples of G1 are defined over GF(p**d1),and ditto G2,d2. All the
other q-division points G clearly have d=lcm(d1,d2) as the least order
such that G\Tp**d = G,and so are defined over GF(p**d).
Tp also acts on the (q+1) subgroups of G of order q. It plainly
leaves((G1)) and ((G2)) invariant: (a1.G1 + a2.G2)\ Tp**r =
a1.k1**r.G1 + a2.k2**r.G2,which is in the same subgroup if and only if
(k2/k1)**r=1. Thus the remaining (q-1)subgroups are invariant precisely
by Tp**r,where r is the order of (k2/k1) in GF(q),and r divides (q-1).
Case 2. The eigevalues k1,k2,lie in GF(q**2) (necessarily distinct).
Proceeding as in case 1,we see that for every q-division point,the
common order d of k1 and k2 is also the least d such that Tp**d is the
identity. Hence all the q-division points are defined over GF(p**d).
We may write d=d+. d-,where k1**d+ is in GF(q) and d+ least,so that
d+ divides q+1 and d- divides q-1.
Also in this case all the (q+1) subgroups of order q are invariant by
Tp**r,where r is the order of (k2/k1) in GF(q**2),and is a divisor of
(q+1). (And in fact r=d+ above).
Case 3. The eigenvalues are equal,i.e.,c= +/-2* sqrt(p) (modulo q).
Case 3.1. The Tp-matrix is a multiple of I,i.e.,every element of G satisfies
g\Tp = k.g. In this case the elements of G all lie in GF(p**d),where d
is the order of k in GF(q),and all the subgroups of G are invariant by
Tp. We have k= +/- sqrt(p) modulo q**2.
Case 3.2 We have G1\Tp = k.G1 and G2\Tp = k.G2 + m.G1 (m.ne.0) . So in this
case G1 has order d,where d is the order of k in GF(q),and so do the (q-1)
nonzero multiples of G1,while all the other members of G are invariant
by Tp**(qd),and so are defined over GF(p**qd). The subgroup generated
by G1 is invariant by Tp,while all the other subgroups are invariant by
Tp**q. We have k = +/- sqrt(p) modulo q.
x-values and y-values of the q-division points.
In general the above analysis as to which extensions the division points
lie in relates to the y-values. If the x-values for some particular set
of q-division points lie in GF(p**d'),then the y-values either lie in the
same field,or in GF(p**d),where d=2*d',and are "pure imaginary" in the
latter. The rules for deciding when the x-values lose this factor of 2
quite simple. In case 1,wheneither d1 or d2 is divisible by 2,the relevan
-t x-values lose a'2'.The "mixed" x-values based on lcm(d1,d2) lose a'2'
if and only if both d1 and d2 are divisible by the same nonzero power
of 2. In cases 2 and 3.2,the'2'is lost when d is divisible by 2.
Examples directly verified by IBM (actual curve unimportant)
p q c eigenvalues theoretical split of y-values/observed split
(orders) of x-values
37 13 -3 4(6) 6(12) 6.6:12: 12 12 12 12 12 12 12 12 12 12 12 12
3.3: 6: 12 12 12 12 12 12
Split of (q+1)-equation 1:1: 4 4 4
61 13 -10 -1(2) 4(6) 2.2.2.2.2.2:6.6: 6(24 times)
1.1.1.1.1.1:3.3: 3(24 times)
Split of (q+1)-equation 1: 1: 3 3 3 3
10 . The Classical Situation over the Complex Numbers(Theoretical)
*************************************************
We now revert to Weber,and later to Schoof,and consider for a given
input curve Y**2=X**3 + A*X+ B, where
?
The (q**2-1)/2 values of X corresponding to the (q**2-1) q-division
points satisfy an equation of degree (q**2-1)/2 irreducible over
C(A,B),and in fact over Q(A,B).
In order to describe the logical structure of what follows,I shall for the
time being commit various abuses of language,& regard the X-values as
being in fact modular functions(when in fact it is their ratios that are
modular functions.) Then the X-values are functions on G1(q),i.e.,
Gammasubone(q) defined as transformations congruent to (1 *; 0 1) mod q.
G1(q) is normal of index (q-1)/2 in G0(q) (gammasubzero(q)) with cyclic
factor group,which in its turn
is of index (q+1) in the modular group with no further
intervening subgroups. The function field equation F(A,B,x)=0 of degree
(q**2-1)/2 and coefficients in Q,with Galois group PGL(2,q) over Q(but
PSL(2,q) over C and indeed over Q(sqrt(q.(-1/q)))),gives
rise when A and B are specialised to a number field of degree (q**2-1)/2.
In this field,the rational prime p splits as described in the previous section;
the factorization of F=0 modulo p into irreducible components gives precisely
the degrees there found. Further,the symmetric functions of the X-values
belonging to any of the (q+1)subgroups will be functions on G0(q),and the
if we have a chain of equations H(x,f,j)=0 of degree (q-1)/2 in x,and
K(f,j)=0 of degree (q+1) in f,then the factorization of K(f,j0)=0 mod p
will have the degrees prescribed in the section above.
Now the application of these ideas merely based upon knowledge of
the degrees of the factors of K has already been used and explained in (A).
The critical idea of Elkies is as follows. In cases 1 and 3,there are 2
or (1 or q+1) linear factors modulo p for K=0. The corresponding X-values
now satisfy an equation of degree (q-1)/2 over GF(p),which must be a product
of equal degree irreducible components of F=0 modulo p. If we can find this
equation,we can carry out Schoof's program with an equation of degree (q-1)/2
rather than (q**2-1)/2.
Thus the first step is to find an equation such as K=0,considered
as an equation of degree (q+1) in f,and find whether it has 0,1,2,or (q+1),
linear factors. If 0,we revert to (A). Otherwise we have found a particular
embedding modulo p of the function field for G0(q),and every function on
G0(q) must be a rational function of f and j,and so determinable modulo p
for this embedding. Hence if we actually knew in some canonical sense the
form of the equations H,we could exhibit the X-values as an equation of
degree (q-1)/2 over GF(p). This is however impracticable.
What in fact succeeds,and is described in Charlap et al. pages 7-10
,is to use general modular theory to find E4(q.tau),E6(q.tau),and
E2Q(tau),and then to use these to find the equation of the X-values. It is my
opinion that the methods they suggest for the first step are quite impracticabl
e,although I have gratefully incorporated their algorithm for deriving the
X-values.
11. Elliptic Functions and the q-Division Points.
***********************************************************
Let us first fix notation. The Weierstrass function P(z) has periods w1,w2,
with Im(tau=w2/w1).gt.0. Let
P(z) = z**(-2) + sigma(k=1,&)c(k).z**(2k) ,
P'(z)**2 = 4.P(z)**3 - g2.P(z) -g3 ,
P''(z) =6.P(z)**2 -g2/2 .
We also need the Weierstrass zeta-function
zeta(z) = 1/z - sigma(k=1,&)c(k)*z**(2k+1)/(2k+1) , zeta'(z)= -P(z) ;
zeta(z+w1)=zeta(z)+ eta1, zeta(z+w2) =zeta(z) + eta2, where
eta1*w2 -eta2*w1= 2*pi*i .
Given g2,g3,we find c(1)=g2/20, c(2)= g3/28, and recursively
(k-2)*(2k+3)*c(k)/3 =sigma(h=1,k-2)c(h)*c(k-1-h) for k.ge.3 .
The elliptic curve Y**2= 4.X**3 -g2*X - g3 is parametrized by
X=P(z),Y=P'(z). We are interested in the particular set of q-division
points z=r.w1/q,where r runs over a complete system modulo q excluding
zero;usually r=1,2,3,...,q-1, or r=+/- 1,2,3,...,(q-1)/2=d. Denote by
P^(z),zeta^(z),g2^,g3^,eta1^,eta2^^,c^(k),the functions and
constants defined by the periods w1/q and w2.
Then using zeta(z+a) + zeta(z-a)=2*zeta(z) + P'(z)/(P(z)-p(a)) and
Tannery and Molk,Fonctions Elliptiques,Tome II,"FORMULES." XXI (3) with r=
+/- 1,2,3,...,(q-1)/2, we see that
zeta^(z) =q*zeta(z) + sigma(r=1,d) P'(z)/(P(z)- P(r*w1/q)) +2*z*S1,
where S1=sigma(r=1,d)P(r*w1/q). (11.1)
In this,replace z by z+w2,and subtract; we find
eta2^ = q*eta2 +2*w2*S1 , or S1= (eta2^ -q*eta2)/(2*w2) . (11.2)
We now integrate the above identity involving zeta-functions,and exponentiate
(of course we are merely using Weierstrass sigma-functions in a sense,but there
was no need to introduce them formally),yielding
z**(1-q)*exp(sigma(k=1,&)z**(2k+2)*(c(k)*q-c^k)/((2k+1)*(2k+2)) +S1*z**2) =
Product(r=1,d) (P(z) - P(r*w1/q)) . (11.3)
The equation for the X-values of the q-division points is
X**d + a(1)*X**(d-1)+...+a(d)= 0 = Product(r=1,d)(X- P(r*w1/d)). (11.4)
Thus we can obtain the values of the a(r) by expanding the exponential
in the LHS of (11.3)in powers of z**2 up to z**(2d),and matching powers
of P(z) similarly expanded: a check is obtained by taking powers z**(2d+2),
etc.(and at least one such check is a part of our method later).
This section more or less follows (CCR) pages 7-10. They use the
derivative of our equation (11.1),which is TM FORMULES XXI (4),and
obtain the power sums of the P(r*w1/q),which need converting back
to the elementary symmetric functions; and also need a separate
derivation of (11.2). The above is slightly quicker both for man
and machine. While we are thinking here of q prime,this section is
valid for any odd q(and with small changes for even q).
The entire computation can be carried out modulo a prime P
PROVIDED that P has no prime factor less than or equal to 2d+2=q+1(
or q+3 if a check is needed). For prime P this is hardly an objectio
-n, but for large finite fields of small characteristic it is,and I
have not been able to counter it by any alternative method.This
point is also made in (CCP).
12. Modular Equations and the Transition to the Isogenous Curve.
*****************************************************************
It will be convenient here to deal strictly with modular forms and functions
(that is,in the inhomogeneous variable tau=omega2/omega1),and to defer to the
next section the interface with the appropriate q-division points. Thus
given our Y**2=X**3+A*X+B,we shall there identify E4=E4(tau) as -A/3
and E6=E6(tau) as -B/2. For now it is enough to know that A and B
define E4 and E6 uniquely; from these we define Delta and j
with the known Fourier expansions in terms of x=exp(2*pi*i*tau) (not the
"x" of the X-equation,of course).
Differentiation with respect to tau we shall perform as
x.d/dx acting on the Fourier series(using Littlewood's convention that 2*pi*i
=1),so that ' denotes x.d/dx . We also need the nonmodular "form" E2
defined by
E2 = 1 -24.sigma(n=1,&)x**n.sigma1(n).
With this notation we have the following list of formulae; all readers
will know some,and some all,but we try to be complete.
1728.Delta = E4**3-E6**2
j = E4**3/Delta , j-1728 = E6**2/Delta ;
j'/j= -E6/E4 , j'/(j-1728)=-E4**2/E6 , j'= -E4**2.E6/Delta ;
Delta'/ Delta =E2 , 3E4'/E4= E2 - E6/E4 , 2E6'/E6 = E2 -E4**2/E6 ;
12E2' = E2**2 - E4.
(Functions and forms relating to G0(q) )
We do not exactly follow the notation of (A)section 2.3. Let
eta(tau)= x**(1/24) (1 -x -x**2+x**5+...),so that eta**24=Delta,
and write s= 12/(q-1,12) , v =s(q-1)/12. Then
F=Fq = q**s.eta**2s(q*tau)/eta**s(tau)
is a function on G0(q) of valence v with a pole only at the cusp zero.
If W=Wq is the canonical involution -1/q*tau,then
F\Wq = q**s/F.
There is a modular equation PHI(F,j)=0, where
PHI=F**(q+1)+Sigma(L=1,q+1)Sigma(R=1,(Lv/q)+1)C(L,R).F**(q+1-L).J**(R-1) .
(Some few C are zero; the computation requires a little technique,
which is described in my first essay. We actually use PHI(q^s/F,j(q.tau))
=0 to get the coefficients.)
We write E2*=F'/F = (q*E2(q*tau)-E2(tau))*s/12 (a modular form),
and E4q= E4(q*tau),E6q=E(q*tau),jq=j(q*tau)=j(-1/(q*tau)).
Our basic problem is: given E4 and E6,to find E2*,E4q,E6q.
******************************************************
(It is of course clear that given any form or function on G0(q) and not on
the full group,we have(with E4 and E6)a basis for expressing any form
on G0(q) rationally in terms of what we know. Thus in theory one could
create a once-for -all list of ad hoc formulae for each q expressing
E4q,E6q,say, in terms of E2*,E4,and E6. For my part I find this less
appealing than what we describe next.)
Using the equation PHI=0 above,this is achieved as follows. Assuming always
that we are in Case 1 or 3 above,we have E4,E6(and hence j,Delta)given,and
also a value of F,obtained by solving PHI=0 for fixed j(which involved,by
the way,taking a square root in Case 1),over GF(p). (Note Delta(q*tau) is
also known using F**(12/s)).
We now differentiate PHI=0 implicitly and obtain E2* as F'/F. A
further differentiation and use of the formulae above gives rise
to E4q(coming from E2* ' )but not E6q; we thus obtain jq=E4q**3/Delta(q*tau).
Now we differentiate PHI at the other cusp(i.e.,PHI(q**s/F,jq)=0),and obtain
E6q as -E4q*q*jq'/jq . Numerous checks are now possible.
********************************************************
Computational considerations lead one in general to prefer the
Star Type modular equation,as described in (A),section 2.2. We now
have PSI(A,j) = 0,where A is "any old function" on G0*(q),of low
valence v on G0*(q),and hence 2v on G0(q). Thus PSI has degree
q+1 in A and degree 2v in j. As before,we have E4,E6,j,Delta,and
a value of A in GF(p).Since A no longer has(like F above)a personal
connection with all the desirable modular forms,we are forced to
differentiate twice at each cusp,and also to solve a further
polynomial equation for linear roots.
Thus first we consider PSI(A,j)=0 as an equation in j
of degree 2v for the fixed A we have chosen modulo p. One root we know
and remove(original j); j(q*tau)=jq is also a root. We find then all
the roots in GF(p) of the above equation(often there is only one),and
try them all in the routine CHARLA in the next section: those that fail
are demonstrably not jq,and the(hopefully,and so far always)one remaining
jq is correct. Notice that the CPU time required for all this is of lower
order of magnitude than the main algorithms' time.
Given now this jq,we differentiate PSI=0 once at each cusp,obtaining
A' and E6q/E4q ; using (j-1728)/j= E6**2/E4**3 this leads to E4q and E6q.
Now we differentiate again at each cusp and eliminate A'' ; after the
mud settles we find we can see E2*. As stated above,this set (E2*,E4q,E6q)
is now tried in CHARLA,for all possible values of jq.
*****************************************************
We also discuss here the alternative modular equation suggested by (CCR).
They use an equation of degree (q+1) in E2*,whose coefficients are forms
of appropriate weights expressible in terms of E4 and E6 (or,by applying
Wq, in terms of E4q and E6q). In the equivalent of cases 1 and 3 above,they
find a value of E2* in GF(p). The procedure with which they then continue
is however intolerably long,and a better continuation is as follows.
Differentiate their equation twice at the cusp infinity(i.e.with
E2*,E4,E6);the first time we get E4q,and the second E6q.
The number and size of the terms in their modular equation are also
larger than those in mine,especially when q=11(mod 12). In that case,
the cuspform eta**2(tau)*eta**2(q*tau) could be used instead of E2*
to form the modular equation. This both saves on size and number of
coefficients,and has convenient derivatives; the reader can by now
easily work out the precise algorithm.
13. The Modular-Elliptic Interface
***************************************************************
14. The Final Calculations.
***************************************************************
We now have a monic equation of degree (q-1)/2 with coefficients in
GF(p) whose roots are the appropriately normalized X-coordinates of the
chosen set of (q-1) q-division points. Tp acting on these division points
has eigenvalue k,say,and if d is the order of k mod q,then our equation
of degree (q-1)/2 is equivalent to d' irreducible equations of degree
d/(d,2)=d*,where d*d'=(q-1)/2. However,it is not advantageous to find thes
e.
We work with the elliptic curve Y**2=X**3 + A*X +B ,and X defined by our
(q-1)/2 degree equation,so that (X,Y) is formally one of our q-division
points. Computations are carried out on the curve with the X-coordinate
always a polynomial in X,and the Y-coordinate either a polynomial in x,
or Y*polynomial in X. The heaviest labour is forming inverses with
polynomial Euclid,not Lehmerized(for my time is also valuable).Legally
the algorithm is : find k in (1,q-1) such that (x**p,y**p)=k.(x,y)
We achieve this as follows.
First form y**p as y*(polynomial in x). This takes very little
longer than x**p(and in fact the time is clearly about 1/4 of that
for the initial modular equation x**p). Then successively form (x,y),
(x2,y2)=2(x,y),(x3,y3)=3.(x,y),...,up to (q-1)/2.(x,y).We must
find a match y**p=yk or -yk=y(-k) for some k in 1.le.k.le.(q-1)/2.
The expectation is that there should only be one match,and if
this could be proved or cheaply established ad hoc,one could exit as
soon as a match was found. However it seems just possible to have an
extraordinary accident where more than one x fits the matching y.
We know of course that there is only one match with x**p and y**p
together,but to confirm this requires the computation of x**p.(And
note that to take x**p as one's basic match is unsound,since there are alw
two possible values of y). However for large q and p,the cost of forming
successive multiples of (x,y) is extremely high,even with a 50% saving
from doing m,n,m+/-n successively. So it may sometimes be worth computing
both x**p and y**p; then of course one can use baby-giant steps to finish
the match. Finally one can cut corners by exiting anyway when the match
on y is found,and hope to complete the formal proof otherwise.
General Considerations of Tactics and Strategy
***************************************************************
I shall at first confine myself to a serial machine;the problem is
very different if the work can be distributed.
TIMING DATA
prime of 130 dd. Primes Total CPU" Modular Eqn CPU"
(Atkin primes all 3-137 9545 243
computd out:Elkies 139-167(6) 8709 1044
primes exit at 173-193(5) 10104 602
first match) 197,199 5173 652
211 3565 599
(break down: modular eqn x**p-x blqmat blppow in CPU")
197 341 1440 670 145 (exit at degree
199 310 1495 687 89 (exit at degree 40)
*********************************************************************
Prime of 150 decimal digits
(Summary of separate runs: elkies out at eigval. !=no atkinq)
Primes Total Time(i/c meqn) " Modular Equation Time "
3-137(32) 12855 241
139-163(5) 10968 593
167-191(5) 11537 432 !
193-211(4) 13350 1413 !
223 4405 668
227 5307 218 (see below)
229 4344 378
233 3575 677
239 3167 114
241 5587 477
251 6382 128
(Concluding sort and match: 159" )
Total time: 81636"=22.7 hours
Total Modular equation time: 5339"=1.48 hours(=6.54% of total)
*********************************************************************
prime modular eqn" x**p-x " elkies y**p elkies match total
.(#=BLQMAT :$=slow version without BLNMAT: #=BLPPOW)(exit eigval/degree)
139 41 1049 277 171 (32) 1557
149 56 1197 #361 #78 (50)
151 32 1229 323 473 (72)
157 127 1326 #1101 $ 2 (2)
163 338 1428 #1233 $ 76 (41)
167 30 1506 393 673 (83)
173 85 1612 abandoned
179 40 1731 abandoned
181 213 1761 abandoned
191 54 1959 507 950 (90)
193 158 1992 518 193 (20) 2877
197 343 2097 540 979 (87)
199 311 2123 abandoned
211 600 2396 617 442 (36)
223 668 2653 684 359 (27) 4405
227 218 7170!! 708 1585 (106) !!=NOBLNMAT
(should have been: 2761 with 5950K storage)
229 378 2790 723 425 (30) 4344
233 677 2886 abandonded 3575
239 114 3039 abandonded 3167
241 477 3090 795 1195 (72) 5587
251 128 3346 863 1990 (109) 6382
*****************************end of 150-digit data***************
Modular Equation Timings on IBM 3090 fast processor UIC March 1992
q v #Chinese #coefficients Time per prime Total Time
(seconds) (seconds)
37 2 4 134
43 2 4 155 .1
53 2 5 190 .232 1.11
61 2 4 218
73 3 5 371
79 2 6 281 .51 3.07
83 2 5 295 .56 2.78
89 2 6 316 .61 3.64
97 4 10 638 2.42 24.2
101 2 6 358 .83 4.97
103 3 8 521 1.66 13.3
107 3 6 541 1.72 10.4
109 3 10 551 1.82 18.2
113 4 9 742 2.92 26.3
127 4 11 833 3.45 38.2
131 2 7 463 1.64 11.5
137 5 11 1105 6.55 72.0
139 4 8 911 5.0 41.1
149 4 10 976 5.7 57
151 3 10 761 3.2 32
157 6 11 1502 11.46 126.8
163 7 18 1805 18.69 337.5
167 3 8 841 3.67 29.6
173 4 12 1132 6.99 84.9
179 3 7 901 5.65 39.6
181 6 12 1703 17.71 213.2
191 3 9 961 6.04 54.5
193 .... (19) (1666) 8.35 158.5 GEGEN3 VALENCE 16
197 6 17 1882 20.0 341
199 5 24 1601 12.9 310
211 7 21 2333 28.5 599
223 7 20 2465 33.3 667
227 5 11 1825 19.75^20.7 218^ 228.3
(229) .... (24) (2320) 17 378^ 400.2 GEGEN3 VALENCE 19
233 7 19 2575 36.5 677^ 693.
239 4 9 1561 12.8 116.0
(241) .... (25) (2562) 20.3 477^ 506.1 GEGEN3 VALENCE 20
251 4 9 1639 14.37 130.4
257 6 18 2452 34 612.
263 5 12 2113 (St. 969K ) 25.84 310.
269 6 19 2566 36.5 694.
271 6 14 2585 36.9 517.
281 7 16? 3103 (ST.1393K) 50.14
311 5 12 2497 35.96 432.