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:
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}$.
$H$ is an abelian group whose order is close to $p$, or not too much larger than $P$.
$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.]