Return to 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.

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.

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?

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.

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$.

Update: these formulas are the same as for complex multiplication in cartesian coordinates, except they are for integers modulo $p$. $\infty$ is the $y$ axis. Now associativity is less surprising.

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?

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?