# EC cardinality $P^3+c$ with 3 gen $G$, $F = P\cdot G,H=P^2\cdot G$ and 2 random members $M_1+iG+jF+kH=M_2$. How long would it take to find $i,j,k$?

Given a EC with cardinality $$C=P^3+c$$ with $$P$$ a prime $$P \approx \sqrt{C}$$ and $$c>0$$. Out of a given generator $$G$$ we generate two additional generator $$F,H$$ with $$F = P \cdot G$$ $$H = P^2 \cdot G$$

(all would still generate a sequence of length $$P^3+c$$)
Given now a random member $$M_1$$ of that EC we can generate a $$P\times P \times P$$ cube of different members with $$M_1 +i\cdot G+j\cdot F+k\cdot H = V_{M_1ijk}$$ $$i,j,k \in [0,P-1]$$ $$|\{V_{M_1ijk}\}| = P^3$$

Every other random member $$M_2$$ can be produced out of $$M_1$$ with: $$M_2 = M_1+i\cdot G+j\cdot F+k\cdot H$$ $$i,j,k \in [0,P]$$

Question:
Given now two random members $$M_1,M_2$$ how many steps are needed to find the related $$i,j,k$$ (on average time)? How would that work?
Would it be (much) safer if we pick $$P = 2\cdot p+1$$ with $$p$$ a prime?
Would it be (much) safer if we pick three (secret) prime factors $$P_1,P_2,P_3$$ instead? with $$P_1 \cdot P_2 \cdot P_3 \approx C$$

(I'm looking for rough estimates related to $$C,P$$ in ($$O$$-notation). We can e.g. ignore the different bit-length-related impact at 2 number multiplication )

The adversary does know about the used EC, the generators $$G,F,H$$ and their inverses $$G^{-1},F^{-1},H^{-1}$$, the random members $$M_1,M_2$$ and the internal structure. He does not know about $$P,d$$ but as there are not too many options we assume he does know this as well.
He want to find unknown $$i,j,k$$ for random known $$M_1,M_2$$.

Side-question: Are there any restrictions of safe EC which can be used for this? E.g. would M-221 with $$y^2 = x^3+117050x^2+x$$ $$\bmod p = 2^{221} - 3$$ work for this?

Trial:
If we just have a single generator $$G$$ it should take $$O(\sqrt{C})$$ using baby-step-giant-step. If $$P$$ is known $$i,j,k$$ can be constructed out of this.
With $$F,H$$ we could do a surface around $$M_1$$ and a straight line with $$G$$ at $$M_2$$ until an intersection of those. This would take $$O(P^2+P)\rightarrow O(P^2)$$ which would be larger than $$O(\sqrt{C})=O(P\sqrt{P})$$. So $$F,H$$ no help here.
Could those generators $$F,H$$ help to make it somehow faster?

Given now two random members $$M_1, M_2$$ how many steps are needed to find the related $$i,j,k$$ (on average time)?
The problem of finding $$i, j, k$$ is equivalent to the discrete log problem:
• If you can solve the discrete log problem, you can compute $$i, j, k$$ (by computing the discrete log of $$M_2 - M_1$$, and then expressing that discrete log in base $$P$$)
• If you can compute $$i, j, k$$, you can solve the discrete log problem (to compute the discrete log of a point M, you would pick an arbitrary point $$M_1$$, set $$M_2 = M + M_1$$, compute $$i, j, k$$; then, the discrete log of $$M$$ is $$i + jP + kP^2$$
For a curve with no known weaknesses, computing the discrete log is believed to take $$O(\sqrt{C})$$ time; if you select a curve with known weaknesses (e.g. a pairing friendly curve that has a pairing operation into a finite field where the discrete log is easier), then the time to solve your problem also drops accordingly.