# Pairing on elliptic curve

Let $E(\mathbb{F_q})$ - elliptic curve.

$G_1 = E(\mathbb{F_q})[r]$. $|G_1| = r$.

$k$ is minimal such $r | q^k - 1$.

$\pi_q$ - $q$-power Frobenius endomorphism.

$G_2 = E(\mathbb{F_{q^k}})[r] \cap Ker([q] - \pi_q)$.

$\mu_r =$ {$z \in \mathbb{F_{q^k}}: z^r = 1$}.

$f_{s, P} \in \mathbb{F_q}(E)$: div$(f_{s, P}) =s(P) - ([s]P) - (s-1)(O)$.

Let $f_{s, P}^{(q^k - 1)/r}(Q)$ is non-degenerate bilinear pairing from $G_1 \times G_2 \to \mu_r$

Is it true that $r | s$ or $r | (s^k - 1)$ ?

-
Is there any relation between $s$ and $q$? What are $P$ and $Q$? –  Srilakshmi Mar 20 '13 at 20:02
@Srilakshmi $q$ is fixing number. $s$ is so number that $f_{s,P}^{(q^k-1)/r}(Q)$ is non-degenerate bilinear pairing. $P$ is point from $G_1$ and $Q$ is point from $G_2$ –  Alexey Mar 21 '13 at 21:47

The groups $G_1$ and $G_2$ are generated by $P$ and $Q$ respecively. For every $s$, $f_{s,P}$ is the Miller function associated with $s$. In Optimized (lower degree Miller functions) pairing, one imposed condition on $s$ is : $s \equiv q \pmod r$. The integer $k$ is minimal such that $r$ $\mid$ ${q^k-1}$, which implies that $r$ $\mid$ $(s^k-1)$.
It is not necessary condition for $s$. For example $s$ can be folowing: $s = q^i($mod$r)$. (google.ru/…) –  Alexey Mar 23 '13 at 13:47