Is it right about an example of bilinear map $e$? The equation for the elliptic curve is $y^{2} = x^{3} + x$ and is defined over the field $F_{q}$ for some prime $q\equiv 3 \pmod 4$, and set $q=307$. Choose random generator $g=[182, 240]$. My question is that how do I construct a bilinear map $e$ and compute $g_{1} = e(g, g)$?
The simplest construction that I know of is given in Section 6.9 of the book by Hoffstein, Pipher and Silverman (5.9 in the first edition). I also talk about it in Section 3.3 of this (but I do not claim that it matches the book's quality of exposition).

First, you need a prime $p$ with two properties:


You want $p\equiv 2\pmod 3$, this allows you to easily construct a supersingular curve over $\mathbf{F}_p$ (as $Y^2 = X^3 + b$ for any $b \ne 0$). Remember that a supersingular curve is one which has $p+1$ points.
You want $p+1$ to have a large prime factor, ideally $q = (p+1)/6$ should be prime. This allows you to pick a point of large prime order. In fact, it is best to first choose a prime $q$ of appropriate size, and then look for a suitable $p$.


For this example, I take $p = 587$ and $b = 1$. Then $q = (p+1)/6 = 137$ is prime, and the point $P = [332,103]$ has order $q$ on the curve $E$ with equation $Y^2 = X^3 + 1$ over $\mathbf{F}_p$. I note $E(K)$ the goup of points of $E$ with coordinates in $K$ ($K$ will be either $\mathbf{F}_p$ or $\mathbf{F}_{p^2}$.)

The basic tool is the Weil pairing, which I will note $e_q$. All you need to know about it is that it is a bilinear map from the group of $q$-torsion points of the curve (i.e., the group of points $P$ such that $qP = \infty$) to the group of $q$th roots of unity in $\mathbf{F}_p$ (i.e., the group of all $x\in \mathbf{F}_p$ such that $x^q = 1$). You can use many computer algebra systems to compute the Weil pairing, I use Pari/GP:

gp &gt; p = 821;
gp &gt; p%3
2
gp &gt; isprime(p)
1
gp &gt; q = (p+1)/6
137
gp &gt; isprime(q)
1
gp &gt; E = ellinit([0,1]*Mod(1,p));
gp &gt; until(ellorder(E,P) == q, P = random(E));
gp &gt; P
[Mod(332, 821), Mod(103, 821)]
gp &gt; ellweilpairing(E,P,P,q)
Mod(1, 821)


However, the Weil pairing is not suitable as is for cryptographic purposes because it is also alternating, meaning that $e_q(P,P) = 1$ for all $P$, so we need to modify it. What we do is consider the curve as being defined over $\mathbf{F}_{p^2}$, and apply the Weil pairing in this curve. More precisely, it we let $\zeta$ be a primitive $3$rd root of unity in $\mathbf{F}_{p^2}$ (prove that it exists), then for any point $P = [x_P,y_P] \in E(\mathbf{F}_p)$, the point $P' = [\zeta\cdot x_P,y_P]$ is in $E(\mathbf{F}_{p^2})$. Moreover, if $qP = \infty$, then $qP' = \infty$ as well, which means that $P'$ can be an "argument" of $e_q$. Hence, finally, we define our "modified Weil pairing" $\hat{e}_q$ on the original curve (over $\mathbf{F}_p$) as follows: for a point $Q = kP$ (for some integer $k$), we let
$$\hat{e}_q(P,Q) = e_q(P,Q'),$$
where $e_q$ is the ordinary Weil pairing, but applied on the curve over $\mathbf{F}_{p^2}$. In practice:

gp &gt; u = ffgen(p^2, u);
gp &gt; until(z != 1, z = random(u)^((p^2-1)/3));
gp &gt; E2 = ellinit([0,1],u);
gp &gt; ellmodweilpairing(E,P,Q,q) = ellweilpairing(E2,P,[z*Q[1],Q[2]],q);
gp &gt; ellmodweilpairing(E,P,P,q)
562*u + 172


We can see that this pairing is bilinear:

gp &gt; Q = ellmul(E,P,99);
gp &gt; ellmodweilpairing(E,P,P,q)*ellmodweilpairing(E,P,Q,q)
693*u + 108
gp &gt; ellmodweilpairing(E,P,elladd(E,P,Q),q)
693*u + 108