# Abelian groups related to $(\mathbb{Z}/p\mathbb{Z})^*$, with order close to $p$ — analogous to elliptic curve groups, but simpler

I'm looking for a construction of a group $H$ that is "a sister" to $(\mathbb{Z}/p\mathbb{Z})^*$, in the following rough sense:

1. Each element of $H$ can be represented by one or a few elements of $\mathbb{Z}/p\mathbb{Z}$ (possibly together with some auxiliary information), and $H$'s group operations (multiplication, inverse, pick a random element of $H$) can be computed using a few field operations from $\mathbb{Z}/p\mathbb{Z}^*$. Computing the group operations in $H$ should not require knowledge of $p$ directly, merely the ability to work in $\mathbb{Z}/p\mathbb{Z}$.

2. $H$ is an abelian group whose order is close to $p$, or not too much larger than $P$.

3. $H$ is elementary and can be described relatively simply. (It should not need fancy machinery or a huge buildup.)

Here $p$ is a prime.

Maybe this is easier to explain with a few examples:

• $(\mathbb{Z}/p\mathbb{Z})^*$ satisfies all these requirements. Obviously, you can compute group operations directly. Its order is $p-1$, and it is simple to explain.

• An elliptic curve $H=\mathbb{E}(\mathbb{Z}/p\mathbb{Z})$ defined by some equation $y^2 = x^3 + ax + b$ (all modulo $p$) is another example. Each element of $H$ can be represented as a pair of elements of $\mathbb{Z}/p\mathbb{Z}$. The group law can be computed using a few operations on $\mathbb{Z}/p\mathbb{Z}$. The group order is a number near $p$. Unfortunately, this is not elementary: it requires a bunch of setup to learn about elliptic curves.

• I think there might be another group $H$ based upon Lucas sequences, defined by $V_0=2$, $V_1=A$, $V_j=AV_{j-1} - V{j-2}$ (all taken modulo $p$) and where $A$ is chosen so that the Jacobi symbol $(A^2-4/p)$ is $-1$. An element of $H$ is a value in the Lucas sequence. We have the relation $V_{2n} = V_n^2 - 2$, so then I think it might be possible to define the group operation of $H$ so that $h^2$ can be computed from $h$ in the way that $V_{2n}$ can be computed from $V_n$ (the one thing I don't know is how to define the multiplication operation). I have a suspicion this might lead to a group of order $p+1$, but I'm not sure. This is not super-elementary, though, and I'm not sure whether it is possible to fill in the details to make this work -- maybe you can fix this idea up.

Does anyone know of any other examples for sister groups $H$? (Preferably ones where the group order is something other than $p-1$, as I already know an examples for that.)

[Motivation: each group $H$ has a chance of leading to a factoring method. For instance, the first example leads to the $p-1$ factoring algorithm, while the second example leads to the elliptic curve (ECM) factoring algorithm. I was hoping to find some simpler, more elementary examples than elliptic curves as a way of introducing the conceptual idea behind the ECM factoring algorithm, without requiring to explain all of the machinery behind the theory of elliptic curves. Thus my request for a group $H$ that requires less mathematical background to understand.]

-
Don't forget the additive group $\mathbb{Z} / p \mathbb{Z}$! Your example, if you're describing Williams' $p+1$ correctly, corresponds to the subgroup of $\mathbb{F}_{p^2}^*$ of order $p+1$. – Hurkyl Jan 25 '13 at 17:50
I have the feeling that your proposed example $H$ can be realised as the subgroup in $GL_2(\mathbb{F}_p)$ generated by a single element. Its entries would correspond to Lucas numbers, and it corresponds to the subgroup as in Hurkyl's comment. So you could try looking at small Abelian subgroups of $GL_n(\mathbb{F}_p)$. – Tib Jan 26 '13 at 18:02

There is a rather general theorem saying that affine algebraic groups over the finite field with $p$ elements are all built from groups of orders $p-1$, $p$ or $p+1$. The case of order $p-1$ is the classical residue class group, that of order $p$ the additive group, and that of order $p+1$ a group constructed from finite fields with $p^2$ elements, Lucase sequences, or conics. These lecture notes, for example, explain how to factor integers with the unit circle.

If you want groups different from that, you have to consider projective algebraic groups, that is, abelian varieties, the simplest case of which are given by elliptic curves.

-