# Pohlig-Hellman on ECDLP over extension field $\mathbb{F_p}^6$

Suppose there is an elliptic curve $$E$$ in form $$y^2=x^3+b$$ defined over $$\mathbb{F_p}$$, where $$p$$ is large prime. #$$E(\mathbb{F_p})$$ is also a large prime but #$$E(\mathbb{F_p})\ne p$$. ECDLP on this curve is in the form of $$Q=[k]P$$. Now let's define the same curve but over extension field $$\mathbb{F_p}^6$$. #$$E(\mathbb{F_p}^6)$$ is composite with many small primes (this composite number for sure is divided by #$$E(\mathbb{F_p})$$ and factors of an order of sextic twist of $$E$$). $$P$$ on $$E$$ over $$\mathbb{F_p}^6$$ have the same prime order as it has on curve over $$\mathbb{F_p}$$.

Can I use Pohlig-Hellman algorithm to solve $$k$$ on curve $$E$$ over $$\mathbb{F_p}^6$$?

• Pohlig-Hellman requires all factors of the order to be small enough to be brute-forceable with an $O(\sqrt q_i)$ algorithm. Given that $p$ is big and #$E(\mathbb F_p)$ is roughly the same bitlength as $p$ and #$E(\mathbb F_p)$ divides #$E(\mathbb{F_p}^6)$, this sounds unlikely? – SEJPM Jun 20 at 12:40
• But if I know something about $k$ for example $k<x$ where $x$ is known there is a possibility to omit largest factors of #$E(\mathbb{F_p}^6)$. But I have doubts about orders. Pohlig-Hellman is applicable if #$E(\mathbb{F_p}^6)$ is not prime or order of $P$ is not prime? Because in this case #$E(\mathbb{F_p}^6)$ is composite, but order of $P$ is prime. – NET_BOT Jun 20 at 13:06