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.