Dividing point on composite order elliptic curve

154 Views Asked by At

Suppose I have elliptic curve $E(\mathbb{F}_{q^m})$ where $q$ is large prime and $m>0$.

Let $N = \#E(\mathbb{F}_{q^m})$ be the order of the group of $\mathbb{F}_{q^m}$-rational points on $E$ with known factorization $N=p_1p_2...p_n$. Suppose that a point $P \in E(\mathbb{F}_{q^m})$ have order $p_1$ generating a cyclic subgroup of order $p_1$. As far as I know there exists a point $Q$ of order (for example) $p_1p_2$ such as $[p_2]Q=P$ (from Lagrange's Theorem).

The point $Q$ is a member of a subgroup of order $p_1 p_2$ but due to composite order it can be cyclic or isomorphic to two cyclic group product (and this subgroup contains subgroup of orders: $p_1$, $p_2$).

My question is knowing $P,p_1,p_2$ is it possible to obtain $Q$? Multiplying $P$ by multiplicative inverse of $p_2$ gives correct answer, but the $Q$ obtained in this way has order the same as $P$. I am wondering whether it is possible to obtain $Q$ of order $p_1p_2$? Something I can lift from a subgroup of order $p_1$ to subgroup to order $p_1p_2$

1

There are 1 best solutions below

0
On

This could not be a comment, so it became a pragmatic pessimistic answer, based on examples. The short (theoretical) answer would be as follows. The problem is stated in full generality. So assume as a particular testing case the situation of an order $N=2p'$ with a "big prime $p'$". The question asks for a generator, knowing a point $T$ of order two. This information is often useless, because a point of order two should be easy to exhibit. The answer would be to forget about $T$ and to pick some three random points. Then one of them is a generator or an element of order $p'$. From here, the answer to the question is not far away. But "taking a random point" is - i think - not that what the OP wants. A slightly more complicated situation is when the order is $N=2p'p''$ with "big primes $p',p''$", and we give a point $T$ of order two. Again, picking a random point is not algebraically satisfactory. The answer would be to find the generator of the cyclic group of $E(\Bbb F_q)$, $q$ being a prime power as in the OP.


Let us use an example. We use $q=7^{19}$, a decent prime power. Let $E$ be the elliptic curve given by the affine equation $$ y^2 = x^3+x+3\ . $$ The equation lives already over $\Bbb F_7$, but we consider $F=\Bbb F_q$-rational points. Computer aid (sage / sagemath) gives the following order for $E(F)$:

sage: q = 7^19
sage: F.<a> = GF(q)
sage: E = EllipticCurve(F, [1, 3])
sage: F
Finite Field in a of size 7^19
sage: E
Elliptic Curve defined by y^2 = x^3 + x + 3 over Finite Field in a of size 7^19
sage: E.order().factor()
2 * 3 * 1899815895635743

So $N=2 \cdot 3 \cdot 1899815895635743$. Now we give a point of order $2$...

sage: T = E.point([5, 0])
sage: T.order()
2

And the OP wants to use it, and the realm of the elliptic curve to exhibit a point of order $2\cdot 3$ and/or a point of order $2\cdot 1899815895635743$. Well, for a point of order $6$, we could ad-hoc build the $3$-division polynomial. But for the other prime... The answer would be to put the hands on a generator for $E(F)$, then use it to find generators of each cyclic subgroup. Sage finds easily a generator in the given case, but this is not a structural help.


An other example with a prime base field for $E$. Let $q$ be the first prime after $10^{40}$, it is $q=10^{40}+121$. We use a sample curve $E$ with affine equation $y^2=x^3+x+3$ over $\Bbb F_q$ with order a product of primes.

sage: q = next_prime(10^40)
sage: E = EllipticCurve(GF(q), [1, 3])
sage: E
Elliptic Curve defined by y^2 = x^3 + x + 3 
over Finite Field of size 10000000000000000000000000000000000000121

sage: E.order().factor()
107 * 1493 * 21277 * 2942022711405041447779724857591

sage: G = E.gens()[0]
sage: G
(3319954692286682916522869759795861336784 : 4190726637766954161366614431117150420994 : 1)


sage: import random
sage: P = random.choice([1..106]) * 1493 * 21277 * 2942022711405041447779724857591 * G
sage: P
(440347668407616747148718125313097964557 : 9073404407112443025885502667532473372970 : 1)
sage: P.order()
107

Assume we give the above $P$, and want a $Q$ of order $107\cdot 2942022711405041447779724857591$. I see no structural way to do this, a way that effectively uses $P$ as a starting point. My way would be to take a generator, to build using it an element $P'$ of order $107$, to solve the "elliptic curve discrete log problem representing $P$ as a multiple of $P'$, then construct correspondingly the point $Q$ from the OP. The discrete log problem amounts in the above case to finding the used random multiplier between $1$ and $106$ from above. But in case we are using instead of $107$ a truly big prime, things get complicated (in algorithm and structure), even if we know the order and a generator.

In the above case i can easily find $Q$, using brute force / a loop, but in general...

sage: P1 = 1493 * 21277 * 2942022711405041447779724857591 * G
sage: for k in [1..106]:
....:     if k*P1 == P:
....:         print(f"{k} * P1 = P"); break
52 * P1 = P
sage: Q = 52 * 1493 * 21277 * G

sage: Q
(1911319638634493804534129484672294635348 : 8867662532223448567468600920065568918242 : 1)

sage: 2942022711405041447779724857591 * Q == P
True