Here follows a very rough draft of #pts essay2 : destroy it when the next version comes(or even earlier if you wish). oa ((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. *************************************************************** 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 Section . The Classical Situation over the Complex Numbers 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. Then the x-values ae 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 impractical. 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. 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 x-equation of the appropriate q-division points. Thus given our y**2=x**3+A*x+B,we shall actually identify E4=E4(tau) as -A/3 and E6=E6(tau) as -B/2,with Delta=(E4**3-E6**2)/1728 and j=E4**3/Delta, with the known Fourier expansions in terms of x=exp(2*pie*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*pie*i =1),so that ' denotes x.d/dx . We also need the nonmodular "form" E2 defined by E2 = 1 -24.sigma/1,infinity/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) 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 PHI(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 PHI 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 PHI(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 PHI=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. (.......here will be my version of (CCP) pages 7-10..._) 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*polunomial 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.