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.