I am dealing with MOV algorithm to transform ECDLP to DLP in $GF(p^k)$, but at the first step I have to determine embedding degree k. I have read the definitions of embedding degree, but still I am not sure, how to compute it and what exactly it states for. As far as I understand embedding degree is not equal to the degree of the curve.
I would be grateful, if somebody could clarify, what the embedding degree stands for, and how to calculate.
On
In a $\textbf{MOV/Frey-Rück}$ context;
Let $E$ be an elliptic curve defined over a finite field $\mathbb{F}_q$, let $n$ be a prime dividing $\#E(\mathbb{F}_q)$. The $\textbf{embedding degree}$ of $E$ with respect to $n$ is the smallest integer $k$ such that $n$ divides $q^k - 1$.
Example
Let $E: y^2 = x^3 + 1$ be an elliptic curve defined over $\mathbb{F}_{101}$.
By Hasse/Waterhouse Theorem'; observe that $\#E(\mathbb{F}_q)$ = 101 + 1 = 2*3*17.
Let $n = 17$.
Since $17|101^2-1$ we call $k = 2$ the embedding degree of $E$ with respect to $n$.
My answer will probably not be perfect, but I will try to convey my own understanding.
When you try to implement the MOV attack (or try to guard from it) what you need to do is transfer the discrete logarithm problem from an EC over $\mathbb{F}_p$ to a finite field $\mathbb{F}_{p^k}$.
For this it is important to note that you are not actually embedding the whole EC group but rather just the cyclic subgroup $\langle P\rangle$ generated by the point $P$ which is the base of your logarithm problem (i.e. $P^d=Q$ or in additive terms for an EC $[d]P=Q$).
We assume that the order $|\langle P\rangle |=l$ is prime (this will be true for pretty much all standard ECC applications). And our goal will be to embed $\langle P \rangle$ into the group of roots of 1 over some appropriate $\mathbb{F}_{p^k}$. For this to be possible there must be enough roots of 1 in the appropriate field and this happens when $l|(p^k-1)$. Since we are trying to be efficient we will want the lowest such $k$ which we call the embedding degree (note this should be the embedding degree of $P$ but since there normally is only one reasonable subgroup of an EC for ECC purposes it seems to be often called the embedding degree of the curve).
To find the embedding degree we first note that $l|(p^k-1)$ is the same as saying that $p^k\equiv 1 \mod l$. Wanting the minimal such $k$ is then equivalent to asking for the multiplicative order of $p$ in $\mathbb{F}_l$. Note that since both $p$ and $l$ are prime $p$ must be a unit in $\mathbb{F}_l$. Moreover we get $p^{l-1}\equiv 1 \mod l$ by Fermat's little theorem.
This gives us an upper bound on $k$. Further we can see that the order of $p$ must divide $l-1$ and so factoring $l-1$ gives us all candidates for $k$, which we can then test.