When plugged into our cubic polynomial, each x in F leads to 0, a square, or not a square. If we believe the distribution is pseudo random, and it probably is, we can expect the elliptic group to have a size near r. The maximum size is 2r+1, when each x produces a valid ±y, and ω is brought in. For instance, y2 = x3+2x+1 mod 3 admits 6 solutions, giving an elliptic group of Z7. The smallest group is of course 1, when there are no solutions to the cubic equation, and we are left with only ω. This is illustrated by y2 = x3+2x+2 mod 3. These cases are somewhat pathological. For a random curve and large r, the size of the group will be very close to r. Thus we would not expect one elliptic group to be a proper sugroup of another. Some groups turn out to be isomorphic, as we shall see below.
One root corresponds to the involution in the middle of an even cycle, and three roots come from two even cycles running in parallel. Add any two involutions together and get the third.
There is a catch; is the second elliptic curve valid? Assume 4a3 + 27b2 is nonzero. Multiply through by c12, and4a′3 + 27b′2 is nonzero. Yes, the implied curve is valid.
Is this map a group isomorphism?
Everything is ok when either of the two summands is ω.
Let the sum equal ω. Thus the two summands are inverses, exhibiting y and -y. The map creates inverse points, yc3 and -yc3, so we're ok.
If m is the slope between two points, or the slope of the tangent line, then m is multiplied by c in the second curve. Sure enough, x3 is multiplied by c2, just like x1 and x2. And y3 is multiplied by c3. The map is a group isomorphism.
If a and b define a valid curve, then ac4 and bc6 give the same group. Groups clump together by the nonzero fourth powers of F. Set c to the fourth root of 1 (if F permits), and you can negate b without changing the group.
If F has order 307, or anything 3 mod 4, each square is automatically a fourth power. Groups clump together in families of size 153 for a = 1 or a = 2 (a nonsquare) and various values of b. Of course a could be 0, whence the size of the group is determined by the residue of b as a sixth power. These families have size 51. Thus each entry in the second column in the table below is divisible by 51.
If everything in F is a fourth power and a sixth power, like the complex numbers, then a can be set to 1, or a = 0 and b = 1.
I wrote a small C program to find the order of all elliptic groups mod p. For grins I ran it on p = 307. Here is the distribution of the groups by order. Note that a group of order 289 could be Z289, or Z172. I didn't separate the groups by structure.
| Order | Number of groups |
|---|---|
| 273 | 51 |
| 274 | 459 |
| 275 | 459 |
| 276 | 1224 |
| 277 | 306 |
| 278 | 612 |
| 279 | 765 |
| 280 | 2448 |
| 281 | 459 |
| 282 | 1224 |
| 283 | 765 |
| 284 | 612 |
| 285 | 1530 |
| 286 | 1836 |
| 287 | 765 |
| 288 | 2754 |
| 289 | 969 |
| 290 | 1224 |
| 291 | 1224 |
| 292 | 2652 |
| 293 | 612 |
| 294 | 1224 |
| 295 | 918 |
| 296 | 3366 |
| 297 | 1224 |
| 298 | 1224 |
| 299 | 918 |
| 300 | 2448 |
| 301 | 2295 |
| 302 | 918 |
| 303 | 918 |
| 304 | 3060 |
| 305 | 918 |
| 306 | 3060 |
| 307 | 612 |
| 308 | 1836 |
| 309 | 612 |
| 310 | 3060 |
| 311 | 918 |
| 312 | 3060 |
| 313 | 918 |
| 314 | 918 |
| 315 | 2295 |
| 316 | 2448 |
| 317 | 918 |
| 318 | 1224 |
| 319 | 1224 |
| 320 | 3366 |
| 321 | 918 |
| 322 | 1224 |
| 323 | 612 |
| 324 | 2652 |
| 325 | 1224 |
| 326 | 1224 |
| 327 | 969 |
| 328 | 2754 |
| 329 | 765 |
| 330 | 1836 |
| 331 | 1530 |
| 332 | 612 |
| 333 | 765 |
| 334 | 1224 |
| 335 | 459 |
| 336 | 2448 |
| 337 | 765 |
| 338 | 612 |
| 339 | 306 |
| 340 | 1224 |
| 341 | 459 |
| 342 | 459 |
| 343 | 51 |
When x = 0 then y = 0, so consider the nonzero values of x. We will consider first the squares, and then the nonsquares.
The squares are squared, giving the fourth powers, but that is the same set as the squares. Add or subtract 1 to give a set S. Partition S into S1 (nonsquares) and S2 (squares). Each of these values is multiplied in turn by some square x. Thus there are 2S2 solutions. We have to be a bit careful here; if the cubic comes out 0 then y and -y are not distinct. This can't happen for x3+x, as x would have to be 0 or the square root of -1. So 2S2 it is.
For x3-x x could be 1 or -1. Thus 1 yields a singleton value of y = 0. So there are 2S2 solutions, or perhaps 2S2-1.
Move on to the nonsquares. Square these, and add or subtract 1, and get the same set S, partitioned into S1 and S2. These are multiplied by nonsquares, giving 2S1 solutions. But there could be one more solution, multiplying 0 from S2 by the nonsquare -1.
Put these together and get 2S solutions. S has size (p-1)/2, so we have p-1 solutions. Bring in 0 and ω, and the group has order p+1, or r+1 for any finite field that is 3 mod 4.
Note that s cannot be 0, else the cubic has a double root.
Assume t = 0, giving x3 - s2x. If p = 3 mod 4, |G| = p+1, as we saw earlier. So let p = 1 mod 4.
Relable s as c2u. Looking through every x is like looking through every c2x. Pull out c6 and find x3 - u2x. In other words, we can normalize s down to 1 or our favorite nonsquare u.
Groups come in only 2 sizes here: G = x3 - x and H = x3 - u2x. Both groups have the origin and ω. G has±1,0 and H has ±u,0. Beyond this there is a correspondence. Suppose x does not come out a square in G. Write y2u = x3-x. Multiply through by u3. Thus (yu2)2 = (ux)3-u2(ux). When x fails in G, ux succeeds in H. similarly, if x succeeds in G then ux fails in H. Put this together and |G| and |H| average out to p+1.
Next assume t is nonzero. Normalize s down to 1 or u, where u is our favorite nonsquare. The formula is (x2-1)*(x-t) or (x2-u2)*(x-t). When x = 0 we have 2 solutions iff t is a square. The size of the group bounces all around with various values of t, but always seems to be a multiple of 4.
For a fixed real x, let v = x3+ax+b. The real group has solutions iff v is a square; the outside group has solutions iff v is a nonsquare (or v = 0). The groups typically do not have the same order. For v nonzero, the two solutions wind up in the real group or the outside group. For v = 0 there is one solution, but it appears in both groups. Bring in ω and the order of the real group + the order of the outside group is 2r+2.
Let the norm of z be z + its conjugate. Let the antinorm of z be z - its conjugate. The norm of z is fixed by conjugation, and such a point has to be real. The antinorm of z is negated by conjugation, and such a point has to be outside. Norm and antinorm are both group homomorphisms.
Norm doubles the real group, and antinorm doubles the outside group. Norm maps the outside group to ω, and antinorm maps the real group to ω. In fact these are the kernels. Show that x has to be real, else z and z conjugate have different x coordinates and their sum or difference will not reach ω. To be a valid point on the curve, y is real or imaginary. If in the "wrong" group then it is doubled, and that becomes ω iff y = 0, whence it is also in the right group, that is, the kernel.
The size of the group is kernel times quotient. Let a = 0 and let r (the size of F) be 2 mod 3. The real group has size r+1, as described at the top of this page. The outside group has solutions for x when the real group does not (save x = 0), and it too has size r+1. Therefore the entire group has size (r+1)2.
Recall the earlier analysis of the group when b = 0 and p = 3 mod 4. This has size r+1, and the outside group has size (2r+2) - (r+1) = (r+1), hence the entire group has size (r+1)2.
You can extend this field, if you like, by another square root, and perform the above analysis all over again for the new extension. The two groups sum to 2r2+2. If the inside group is (r+1)2, the outside group is (r-1)2, making the new group (r+1)2(r-1)2.
The converse is (sometimes) true. The points outside this subgroup are all nonsquares for some primes, but for other primes they are 2/3 nonsquares and 1/3 squares.
Note that -s is always a root of the cubic, thus G has even order and the double group inside is proper. The cubic becomes (x+s) × (x2-sx+s2+a). The discriminant is -3s2-4a. This determines whether the cubic splits fully. We have an odd subgroup, cross a power of 2, cross another power of 2 iff the cubic splits fully, iff the discriminant is a square. This is when the double group has index 4, and the points outside are 2/3 nonsquares and 1/3 squares, the squares being the points where the values within the two power 2 cycles are both odd.
As a special case let a = -3s2, whence b = -2s3. This turns our expression 2s2-2sx-x2+a into a square. (I'm assuming p = 1 mod 4 so -1 is a square.) So if 2y is a square the double point has x a fourth power, and if 2y is not a square the double point has x a square but not a fourth power. Unfortunately 4a3 + 27b2 = 0, so it's not really an elliptic curve.
Our homomorphism is not well defined on the root -s, since -s+s is 0, which does not have a valid legendre symbol. In this case you can use a+3s2. This tells us whether -s maps to a square or nonsquare in the homomorphism. I don't know why it works, but a+3s2 is the derivative of as+s3, and that is probably not a coincidence.
Now let's make things a bit more complicated. After doubling a point, ask whether x2+sx+t is a square. Let a = t-s2. Let b = -st. Compute the new x, then x2+sx+t, and get the square of s4 - 2s3x - 2sx3 - x4 - 4s2t - t2 - 6x2t + 6sxt. (Verify with this program.) Note that the degenerate case ( t = s2/4, wherein x2+sx+t is always a square anyways, leads to an invalid elliptic curve with 4a3 + 27b2 = 0.
Note that s is a root, and the cubic becomes (x-s) × (x2+sx+t). The discriminant s2-4t tells us whether there are 2 parallel even cycles.
Again it would be fun to have the above expression be itself a square. Let t = ks2 and then we want k2+4k-1 to be a square. If k is rational we want k2+4kl-l2 to be a square. Let t = s2/4 and that works. We find the square of s2+4sx+x2. But again a = -3s2/4 and b = s3/4 is not valid.
Moving on to cubes, let a = 27s4+6st, and let b = -27s6+t2. Triple any point, and y+3sx+t is a cube. In fact we have a group homomorphism from the elliptic group onto the integers mod 3, with the triple points mapping to 0. I can't prove this algebraically, and have no idea why it works.
Here is another square, and then a fourth power. Let a = t-s2-2r4+3r2s, and let b = -st-r6+2r4s-r2s2+r2t. Double a point, and 2ry+x2+sx+t is a square. (Set r = 0 to get the equation we saw earlier for x2+sx+t). Set t = s2/4-3r2s+3r4, and multiply a point by 4, and our expression 2ry+x2+sx+t becomes a fourth power.