# How hard is the DLP in that simple group?

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.

• How sure are you that this is a group? You are essentially doing Montgomery-curve $x$-only arithmetic in a strange way. I find it hard to believe this thing is associative. – CurveEnthusiast Mar 30 '17 at 16:21
• @CurveEnthusiast: Yes I'm reasonably sure this is a commutative group. Associativity is indeed tricky, but does work. Basic algebra is enough to show that $(a*b)*c=a*(b*c)$ when there is no special case. A tricky case is when $a*b=\infty$ but $b*c\ne\infty$, where we need that there is no square root of $-1$ modulo $p$. But that works. I also checked my results numerically with small examples. – fgrieu Mar 30 '17 at 16:39
• Actually, you can find a generator of the subgroup easier by selecting an arbitrary value $h$, computing $g = h^4$; if that's not INF, that's your generator... – poncho Mar 30 '17 at 19:05
• Is there any other reason for $p = 4q - 1$ other than $-1$ must have no square roots? Because you could use prime $q$, arbitrary $k > 1, p = kq+1$ with $p=3 \mod 4$. – tylo Mar 31 '17 at 11:38
• @tylo: Any prime $p\equiv3\pmod4$ makes $G$ a group. $p=4q-1$ seems to allow the smallest $p$ for a given $q$ order of the prime subgroup , and is kept from my original source. BTW, that's a proposed post-quantum asymmetric cryptosystem, found on sci.crypt Message-ID: <ob5p8q$4dr$1@gioia.aioe.org>. It is neatly described thus falsifiable, and based on a non-commutative and non-associative law with property $(a\star b)\star(c\star d)=(a\star c)\star(b\star d)$; a little analysis showed that it was a variant within sign of the present $*$, and that led to a total break (not requiring the DLP). – fgrieu Mar 31 '17 at 18:06

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.

• No, it's that I found an isomorphism, efficiently-computable exactly in both ways, $\hspace{1.21 in}$ to the (mod-p) circle group itself. ​ ​ – user991 Mar 31 '17 at 6:35
• Nice answer! Milne touches on this group in his notes (jmilne.org/math/Books/ectext5.pdf) in chapter II.3. – CurveEnthusiast Mar 31 '17 at 6:40
• Can you do something similar with f(a,b)=(ab+1)/(a+b)? I'll ask another day if required. The difference is the + sign instead of -. – daniel Apr 2 '17 at 16:02
• @fgrieu : ​ ​ ​ I just fixed a typo that might have been confusing you. ​ The mod-p circle group is obtained by running the rest of the circle group's definition mod-p rather than over the reals. ​ (So, the subset of $x+iy \in (\mathbb{Z}/p\mathbb{Z})[i]$ with $x^2+y^2 = 1$, which forms a group under field multiplication.) ​ ​ ​ ​ ​ ​ ​ ​ – user991 Apr 3 '17 at 0:59
• So the big picture is: the question's $G$ is efficiently isomorphic to the mop-p circle group. The DLP in both is equivalent. That should thus be be amenable to a small variant of index calculus (much like index calculus applies to supersingular Elliptic Curves), and perhaps to some variants of NFS. Thus the DLP in $G$ should not be much harder than the well-studied DLP in $\mathbb Z_p$; we do not have a proof that it's not even easier. – fgrieu Apr 3 '17 at 1:20