Return to Answer

The problem can be restated as: given a twisted Edwards curve over some finite field, $A$, $B$, $G$ on that curve, integers $s_1$ and $s_2$ with $A=s_1\times G$ and $B=s_2\times G$, can we find integer $s$ with $A=s\times B$, and how?

Optionally, we can immediately settle the case $B=\mathcal O$: if $A=\mathcal O$ any integer $s$ will do, otherwise there is no solution.

I'll assume we are given or find the order $m$ of the full curve (always a multiple of $4$), and it's factorization $m=\prod p^{m_p}$ for primes $p$, as is always the case in cryptography. For common curves $m=2^{m_2}\,q$ with $m_2\in\{2,3\}$ and a single large prime $q$, but we tackle the general case.

We find the order $\ell$ of $G$. E.g. we find one by one the multiplicities $\ell_p$ in $\ell=\prod p^{\ell_p}$, using that for each $p$ in the factorization of $m$, $\ell_p$ is the largest $i\le m_p$ such that $p^i\times\left(\left(m/p^{m_p}\right)\times G\right)=\mathcal O$.

Then we turn the problem into arithmetic modulo the (possibly composite) $\ell$: $$\begin{align} A=s_3\times B&\iff s_1\times G=s\times(s_2\times G)\\ &\iff s_1\times G=(s\,s_2)\times G\\ &\iff s_1\equiv s\,s_2\pmod\ell \end{align}$$

Compute $g=\gcd(s_2,\ell)$. If $s_1\bmod g\ne 0$ then there is no solution. Otherwise compute $\ell'=\ell/g\,$, $s_1'=(s_1/g)\bmod\ell'\,$, $s_2'=(s_2/g)\bmod\ell'$. The problem is reduced to $s'_1\equiv s\,s'_2\pmod{\ell'}$ with $\gcd(\ell',s'_2)=1$. Solutions are thus the $$s=\bigl(\left({s'_2}^{-1}\bmod\ell'\right)\,s'_1\bmod\ell'\bigr)+k\,\ell'\ \text{ for }\ k\in\mathbb Z$$ where ${s'_2}^{-1}\bmod\ell'$ is the inverse of $s'_2$ modulo $\ell'$, and can be efficiently computed by the (half-)extended Euclidean algorithm.

Notice that it's not necessary to make any use of the givens $A$ and $B$, and that the only necessary use of the given $G$ is to find it's order.

The problem can be restated as: given a twisted Edwards curve over some finite field, $A$, $B$, $G$ on that curve, integers $s_1$ and $s_2$ with $A=s_1\times G$ and $B=s_2\times G$, can we find integer $s$ with $A=s\times B$, and how?

Optionally, we can immediately settle the case $B=\mathcal O$: if $A=\mathcal O$ any integer $s$ will do, otherwise there is no solution.

I'll assume we are given or find the order $m$ of the full curve (always a multiple of $4$), and it's factorization $m=\prod p^{m_p}$ for primes $p$, as is always the case in cryptography. For common curves $m=2^{m_2}\,q$ with $m_2\in\{2,3\}$ and a single large prime $q$, but we tackle the general case.

We find the order $\ell$ of $G$. E.g. we find one by one the multiplicities $\ell_p$ in $\ell=\prod p^{\ell_p}$, using that for each $p$ in the factorization of $m$, $\ell_p$ is the largest $i\le m_p$ such that $p^i\times\left(\left(m/p^{m_p}\right)\times G\right)=\mathcal O$.

Then we turn the problem into arithmetic modulo the (possibly composite) $\ell$: $$\begin{align} A=s_3\times B&\iff s_1\times G=s\times(s_2\times G)\\ &\iff s_1\times G=(s\,s_2)\times G\\ &\iff s_1\equiv s\,s_2\pmod\ell \end{align}$$

Compute $g=\gcd(s_2,\ell)$. If $s_1\bmod g\ne 0$ then there is no solution. Otherwise compute $\ell'=\ell/g\,$, $s_1'=(s_1/g)\bmod\ell'\,$, $s_2'=(s_2/g)\bmod\ell'$. The problem is reduced to $s'_1\equiv s\,s'_2\pmod{\ell'}$ with $\gcd(\ell',s'_2)=1$. Solutions are thus the $$s=\bigl(\left({s'_2}^{-1}\bmod\ell'\right)\,s'_1\bmod\ell'\bigr)+k\,\ell'\ \text{ for }\ k\in\mathbb Z$$ where ${s'_2}^{-1}\bmod\ell'$ is the inverse of $s'_2$ modulo $\ell'$, and can be efficiently computed by the (half-)extended Euclidean algorithm.

Notice that it's not necessary to make any use of the givens $A$ and $B$, nor or their order, and that the only necessary use of the given $G$ is to find it's order.

If we want to solve for $B=s\times A$ instead of $A=s\times B$, then we can proceed just as in the above solution of the original problem after exchanging $s_1$ and $s_2$.

The problem can be restated as: given a twisted Edwards curve over some finite field, $A$, $B$, $G$ on that curve, integers $s_1$ and $s_2$ with $A=s_1\times G$ and $B=s_2\times G$, can we find integer $s$ with $A=s\times B$, and how?

Optionally, we can immediately settle the case $B=\mathcal O$: if $A=\mathcal O$ any integer $s$ will do, otherwise there is no solution.

I'll assume we are given or find the order $m$ of the full curve (always a multiple of $4$), and it's factorization $m=\prod p^{m_p}$ for primes $p$, as is always the case in cryptography. For common curves $m=2^{m_2}\,q$ with $m_2\in\{2,3\}$ and a single large prime $q$, but we tackle the general case.

We find the order $\ell$ of $G$. E.g. we find one by one the multiplicities $\ell_p$ in $\ell=\prod p^{\ell_p}$, using that for each $p$ in the factorization of $m$, $\ell_p$ is the largest $i\le\ell_p$ such that $p^i\times\left(\left(m/p^{m_p}\right)\times G\right)=\mathcal O$.

Then we turn the problem into arithmetic modulo the (possibly composite) $\ell$: $$\begin{align} A=s_3\times B&\iff s_1\times G=s\times(s_2\times G)\\ &\iff s_1\times G=(s\,s_2)\times G\\ &\iff s_1\equiv s\,s_2\pmod\ell \end{align}$$

Compute $g=\gcd(s_2,\ell)$. If $s_1\bmod g\ne 0$ then there is no solution. Otherwise compute $\ell'=\ell/g\,$, $s_1'=(s_1/g)\bmod\ell'\,$, $s_2'=(s_2/g)\bmod\ell'$. The problem is reduced to $s'_1\equiv s\,s'_2\pmod{\ell'}$ with $\gcd(\ell',s'_2)=1$. Solutions are thus the $$s=\bigl(\left({s'_2}^{-1}\bmod\ell'\right)\,s'_1\bmod\ell'\bigr)+k\,\ell'\ \text{ for }\ k\in\mathbb Z$$ where ${s'_2}^{-1}\bmod\ell'$ is the inverse of $s'_2$ modulo $\ell'$, and can be efficiently computed by the (half-)extended Euclidean algorithm.

Notice that it's not necessary to make any use of the givens $A$ and $B$, and that the only necessary use of the given $G$ is to find it's order.

The problem can be restated as: given a twisted Edwards curve over some finite field, $A$, $B$, $G$ on that curve, integers $s_1$ and $s_2$ with $A=s_1\times G$ and $B=s_2\times G$, can we find integer $s$ with $A=s\times B$, and how?

Optionally, we can immediately settle the case $B=\mathcal O$: if $A=\mathcal O$ any integer $s$ will do, otherwise there is no solution.

I'll assume we are given or find the order $m$ of the full curve (always a multiple of $4$), and it's factorization $m=\prod p^{m_p}$ for primes $p$, as is always the case in cryptography. For common curves $m=2^{m_2}\,q$ with $m_2\in\{2,3\}$ and a single large prime $q$, but we tackle the general case.

We find the order $\ell$ of $G$. E.g. we find one by one the multiplicities $\ell_p$ in $\ell=\prod p^{\ell_p}$, using that for each $p$ in the factorization of $m$, $\ell_p$ is the largest $i\le m_p$ such that $p^i\times\left(\left(m/p^{m_p}\right)\times G\right)=\mathcal O$.

Then we turn the problem into arithmetic modulo the (possibly composite) $\ell$: $$\begin{align} A=s_3\times B&\iff s_1\times G=s\times(s_2\times G)\\ &\iff s_1\times G=(s\,s_2)\times G\\ &\iff s_1\equiv s\,s_2\pmod\ell \end{align}$$

Compute $g=\gcd(s_2,\ell)$. If $s_1\bmod g\ne 0$ then there is no solution. Otherwise compute $\ell'=\ell/g\,$, $s_1'=(s_1/g)\bmod\ell'\,$, $s_2'=(s_2/g)\bmod\ell'$. The problem is reduced to $s'_1\equiv s\,s'_2\pmod{\ell'}$ with $\gcd(\ell',s'_2)=1$. Solutions are thus the $$s=\bigl(\left({s'_2}^{-1}\bmod\ell'\right)\,s'_1\bmod\ell'\bigr)+k\,\ell'\ \text{ for }\ k\in\mathbb Z$$ where ${s'_2}^{-1}\bmod\ell'$ is the inverse of $s'_2$ modulo $\ell'$, and can be efficiently computed by the (half-)extended Euclidean algorithm.

Notice that it's not necessary to make any use of the givens $A$ and $B$, and that the only necessary use of the given $G$ is to find it's order.

The problem can be restated as: given a twisted Edwards curve over some finite field, $A$, $B$, $G$ on that curve, integers $s_1$ and $s_2$ with $A=s_1\times G$ and $B=s_2\times G$, can we find integer $s$ with $A=s\times B$, and how?

Optionally, we can immediately settle the case $B=\mathcal O$: if $A=\mathcal O$ any integer $s$ will do, otherwise there is no solution.

I'll assume we are given or find the order $m$ of the full curve (always a multiple of $4$), and it's factorization $m=\prod p^{m_p}$ for primes $p$, as is always the case in cryptography. For common curves $m=2^{m_2}\,q$ with $m_2\in\{2,3\}$ and a single large prime $q$, but we tackle the general case.

We find the order $\ell$ of $G$. E.g. we find one by one the multiplicities $\ell_p$ in $\ell=\prod p^{\ell_p}$, using that for each $p$ in the factorization of $m$, $\ell_p$ is the largest $i\le\ell_p$ such that $p^i\times\left(\left(m/p^{m_p}\right)\times G\right)=\mathcal O$.

Then we turn the problem into arithmetic modulo the (possibly composite) $\ell$: $$\begin{align} A=s_3\times B&\iff s_1\times G=s\times(s_2\times G)\\ &\iff s_1\times G=(s\,s_2)\times G\\ &\iff s_1\equiv s\,s_2\pmod\ell \end{align}$$

Compute $g=\gcd(s_2,\ell)$. If $s_1\not\equiv 0\pmod g$ then there is no solution.

  Otherwise compute $\ell'=\ell/g\,$, $s_1'=(s_1/g)\bmod\ell'\,$, $s_2'=(s_2/g)\bmod\ell'$. The problem is reduced to $s'_1\equiv s\,s'_2\pmod{\ell'}$ with $\gcd(\ell',s'_2)=1$. Solutions are thus the $$s=\bigl(\left({s'_2}^{-1}\bmod\ell'\right)\,s'_1\bmod\ell'\bigr)+k\,\ell'\ \text{ for }\ k\in\mathbb Z$$ where ${s'_2}^{-1}\bmod\ell'$ is the inverse of $s'_2$ modulo $\ell'$, and can be efficiently computed by the (half-)extended Euclidean algorithm.

The problem can be restated as: given a twisted Edwards curve over some finite field, $A$, $B$, $G$ on that curve, integers $s_1$ and $s_2$ with $A=s_1\times G$ and $B=s_2\times G$, can we find integer $s$ with $A=s\times B$, and how?

Optionally, we can immediately settle the case $B=\mathcal O$: if $A=\mathcal O$ any integer $s$ will do, otherwise there is no solution.

I'll assume we are given or find the order $m$ of the full curve (always a multiple of $4$), and it's factorization $m=\prod p^{m_p}$ for primes $p$, as is always the case in cryptography. For common curves $m=2^{m_2}\,q$ with $m_2\in\{2,3\}$ and a single large prime $q$, but we tackle the general case.

We find the order $\ell$ of $G$. E.g. we find one by one the multiplicities $\ell_p$ in $\ell=\prod p^{\ell_p}$, using that for each $p$ in the factorization of $m$, $\ell_p$ is the largest $i\le\ell_p$ such that $p^i\times\left(\left(m/p^{m_p}\right)\times G\right)=\mathcal O$.

Then we turn the problem into arithmetic modulo the (possibly composite) $\ell$: $$\begin{align} A=s_3\times B&\iff s_1\times G=s\times(s_2\times G)\\ &\iff s_1\times G=(s\,s_2)\times G\\ &\iff s_1\equiv s\,s_2\pmod\ell \end{align}$$

Compute $g=\gcd(s_2,\ell)$. If $s_1\bmod g\ne 0$ then there is no solution. Otherwise compute $\ell'=\ell/g\,$, $s_1'=(s_1/g)\bmod\ell'\,$, $s_2'=(s_2/g)\bmod\ell'$. The problem is reduced to $s'_1\equiv s\,s'_2\pmod{\ell'}$ with $\gcd(\ell',s'_2)=1$. Solutions are thus the $$s=\bigl(\left({s'_2}^{-1}\bmod\ell'\right)\,s'_1\bmod\ell'\bigr)+k\,\ell'\ \text{ for }\ k\in\mathbb Z$$ where ${s'_2}^{-1}\bmod\ell'$ is the inverse of $s'_2$ modulo $\ell'$, and can be efficiently computed by the (half-)extended Euclidean algorithm.

Notice that it's not necessary to make any use of the givens $A$ and $B$, and that the only necessary use of the given $G$ is to find it's order.