How hard is the DLP in that simple group?

Question

Let $p=4q-1$ be a prime with $q$ an odd prime. Let $G=\{0,1,\dots,p-1,\infty\}$. The following law $*$ makes $(G,*)$ a commutative group of order $4q$ with neutral element $\infty$: $$a*b=\begin{cases} a&\text{if }b=\infty\\ b&\text{if }a=\infty\\ \infty&\text{if }a\ne\infty\text{ and }b\ne\infty\text{ and }a+b\equiv 0\pmod p\\ {ab-1\over a+b}\bmod p&\text{otherwise}\end{cases}$$ The inverse of $a$ for law $*$ is $p-a$, with the exceptions of $0$ and $\infty$ which are their own inverse. Proof of associativity requires care, and uses $p\equiv3\bmod4$ at some point.

Computation can be simplified by keeping an element of $G$ as an integer fraction $x\over y$ with $x$ and $y$ integers modulo $p$, and the neutral element $\infty$ represented as $x\over0$ with $x\not\equiv0\pmod p$. The group law becomes, without any special case: $${x_a\over y_a}*{x_b\over y_b}={(x_ax_b-y_ay_b)\bmod p\over(x_ay_b+y_ax_b)\bmod p}$$ and we need only 4 multiplications, 1 addition, 1 subtraction, and 2 modular reductions for $a*b$; down to 2 squarings, 1 multiplication, 1 doubling, 1 subtraction, and 2 modular reductions for $a*a$.

Since we have a group law, we can define exponentiation. Exponents can be reduced modulo $4q$, the order of the group.

Let $g$ be an element of order $q$. It can be found heuristically, perhaps starting from $g=2$ incrementally and checking $g^4\ne\infty$ and $g^q=\infty$ (Poncho's comment gives a faster way when we don't care that $g$ is large).

Question: How hard is the Discrete Logarithm Problem in the cyclic subgroup of prime order $q$ generated by $g$? Is it somewhat related to a well known group?

---

Update: The formulas $x_{a*b}=(x_ax_b-y_ay_b)\bmod p$ and $y_{a*b}=(x_ay_b+y_ax_b)\bmod p$ are the same as for complex multiplication in cartesian coordinates, except they are for integers modulo $p$. Now associativity is less surprising.

By going thru polar coordinates, we can express of $g^k$ for law $*$ without iteration: that's $((y^{-1}\bmod p)x)\bmod p$ for $x=(g^2+1)^{k/2}\cos(k\cot^{-1}g)$ and $y=(g^2+1)^{k/2}\sin(k\cot^{-1}g)$. Quantities $x$ and $y$ are integers even though intermediate values use reals. This is computationally impractical, because we need so extreme precision. And it does not lead to a trivial way to solve the DLP.

Answer 1

That group embeds in ​ $F_{\hspace{-0.02 in}p}[i\hspace{.02 in}]$$^{\hspace{.02 in}*}$ ​ via the Möbius transformation given by

$f(x) = \dfrac{x+i}{x-i}$ ​ (and ​ $\hspace{.04 in}f(\infty) = 1$ ), ​ and that embedding has a left-inverse

(that is not injective and is not necessarily a homomorphism) which is the

Möbius transformation given by $\;\;\; g(z) \: = \: \dfrac{z+1}{z-1} \cdot i \;\;\;$ (and ​ $g(1) = \infty$ ).


Their partial-inverse-ness can be used to find the range of that embedding
(namely, that range is the set of fixed-points of that embedding composed with $g$);
solving reveals that it's exactly the points $z$ such that $g(z)$ is in the embedding's domain.
Further solving then gives that for all elements $c$ and $d$ of $F_{\hspace{-0.02 in}p}$,
$g(c\hspace{-0.03 in}+\hspace{-0.03 in}(d\hspace{-0.06 in}\cdot \hspace{-0.05 in}i\hspace{.02 in}))$ ​ is in that embedding's domain if and only if $\;\;\; c^{\hspace{.02 in}2}\hspace{-0.04 in}+d^{\hspace{.02 in}2} \: = \: 1 \;\;\;$.

Therefore your group is efficiently-equivalent to the mod-p circle group.


The latter is an efficiently-decidable subgroup of the multiplicative group of an efficient field,
and that efficient field is a simple quotient of the Gaussian integers,
which is a Unique Factorization Domain whose number of units is small.
Thus, by trying to find the discrete log of both inputs in the subgroup with
respect to the same generator of the whole multiplicative group, one should be
able to attack the subgroup's Discrete Logarithm Problem with index calculus,
using $i$ and non-associate Gaussian primes as the factor base.
For that reason, although I don't know how GNFS works, I'd imagine the hardness of
your group's DLP is at most not much more than for the standard DLP mod primes.

I'm not aware of any faster-than-SNFS DLP algorithms for any
[subgroups whose order has a large prime factor] of multiplicative groups of an efficient field, so in particular, I'm also not aware of any such algorithms for your group.
On the other hand, I also don't know how SNFS works.