Bilinear map in mathematics
In mathematics , a pairing is an R -bilinear map from the Cartesian product of two R -modules , where the underlying ring R is commutative .
Let R be a commutative ring with unit , and let M , N and L be R -modules .
A pairing is any R -bilinear map
e
:
M
×
N
→
L
{\displaystyle e:M\times N\to L}
. That is, it satisfies
e
(
r
⋅
m
,
n
)
=
e
(
m
,
r
⋅
n
)
=
r
⋅
e
(
m
,
n
)
{\displaystyle e(r\cdot m,n)=e(m,r\cdot n)=r\cdot e(m,n)}
,
e
(
m
1
+
m
2
,
n
)
=
e
(
m
1
,
n
)
+
e
(
m
2
,
n
)
{\displaystyle e(m_{1}+m_{2},n)=e(m_{1},n)+e(m_{2},n)}
and
e
(
m
,
n
1
+
n
2
)
=
e
(
m
,
n
1
)
+
e
(
m
,
n
2
)
{\displaystyle e(m,n_{1}+n_{2})=e(m,n_{1})+e(m,n_{2})}
for any
r
∈
R
{\displaystyle r\in R}
and any
m
,
m
1
,
m
2
∈
M
{\displaystyle m,m_{1},m_{2}\in M}
and any
n
,
n
1
,
n
2
∈
N
{\displaystyle n,n_{1},n_{2}\in N}
. Equivalently, a pairing is an R -linear map
M
⊗
R
N
→
L
{\displaystyle M\otimes _{R}N\to L}
where
M
⊗
R
N
{\displaystyle M\otimes _{R}N}
denotes the tensor product of M and N .
A pairing can also be considered as an R -linear map
Φ
:
M
→
Hom
R
(
N
,
L
)
{\displaystyle \Phi :M\to \operatorname {Hom} _{R}(N,L)}
, which matches the first definition by setting
Φ
(
m
)
(
n
)
:=
e
(
m
,
n
)
{\displaystyle \Phi (m)(n):=e(m,n)}
.
A pairing is called perfect if the above map
Φ
{\displaystyle \Phi }
is an isomorphism of R -modules.
A pairing is called non-degenerate on the right if for the above map we have that
e
(
m
,
n
)
=
0
{\displaystyle e(m,n)=0}
for all
m
{\displaystyle m}
implies
n
=
0
{\displaystyle n=0}
; similarly,
e
{\displaystyle e}
is called non-degenerate on the left if
e
(
m
,
n
)
=
0
{\displaystyle e(m,n)=0}
for all
n
{\displaystyle n}
implies
m
=
0
{\displaystyle m=0}
.
A pairing is called alternating if
N
=
M
{\displaystyle N=M}
and
e
(
m
,
m
)
=
0
{\displaystyle e(m,m)=0}
for all m . In particular, this implies
e
(
m
+
n
,
m
+
n
)
=
0
{\displaystyle e(m+n,m+n)=0}
, while bilinearity shows
e
(
m
+
n
,
m
+
n
)
=
e
(
m
,
m
)
+
e
(
m
,
n
)
+
e
(
n
,
m
)
+
e
(
n
,
n
)
=
e
(
m
,
n
)
+
e
(
n
,
m
)
{\displaystyle e(m+n,m+n)=e(m,m)+e(m,n)+e(n,m)+e(n,n)=e(m,n)+e(n,m)}
. Thus, for an alternating pairing,
e
(
m
,
n
)
=
−
e
(
n
,
m
)
{\displaystyle e(m,n)=-e(n,m)}
.
Any scalar product on a real vector space V is a pairing (set M = N = V , R = R in the above definitions).
The determinant map (2 × 2 matrices over k ) → k can be seen as a pairing
k
2
×
k
2
→
k
{\displaystyle k^{2}\times k^{2}\to k}
.
The Hopf map
S
3
→
S
2
{\displaystyle S^{3}\to S^{2))
written as
h
:
S
2
×
S
2
→
S
2
{\displaystyle h:S^{2}\times S^{2}\to S^{2))
is an example of a pairing. For instance, Hardie et al.[ 1] present an explicit construction of the map using poset models.
Pairings in cryptography [ edit ] In cryptography , often the following specialized definition is used:[ 2]
Let
G
1
,
G
2
{\displaystyle \textstyle G_{1},G_{2))
be additive groups and
G
T
{\displaystyle \textstyle G_{T))
a multiplicative group , all of prime order
p
{\displaystyle \textstyle p}
. Let
P
∈
G
1
,
Q
∈
G
2
{\displaystyle \textstyle P\in G_{1},Q\in G_{2))
be generators of
G
1
{\displaystyle \textstyle G_{1))
and
G
2
{\displaystyle \textstyle G_{2))
respectively.
A pairing is a map:
e
:
G
1
×
G
2
→
G
T
{\displaystyle e:G_{1}\times G_{2}\rightarrow G_{T))
for which the following holds:
Bilinearity :
∀
a
,
b
∈
Z
:
e
(
a
P
,
b
Q
)
=
e
(
P
,
Q
)
a
b
{\displaystyle \textstyle \forall a,b\in \mathbb {Z} :\ e\left(aP,bQ\right)=e\left(P,Q\right)^{ab))
Non-degeneracy :
e
(
P
,
Q
)
≠
1
{\displaystyle \textstyle e\left(P,Q\right)\neq 1}
For practical purposes,
e
{\displaystyle \textstyle e}
has to be computable in an efficient manner Note that it is also common in cryptographic literature for all groups to be written in multiplicative notation.
In cases when
G
1
=
G
2
=
G
{\displaystyle \textstyle G_{1}=G_{2}=G}
, the pairing is called symmetric. As
G
{\displaystyle \textstyle G}
is cyclic , the map
e
{\displaystyle e}
will be commutative ; that is, for any
P
,
Q
∈
G
{\displaystyle P,Q\in G}
, we have
e
(
P
,
Q
)
=
e
(
Q
,
P
)
{\displaystyle e(P,Q)=e(Q,P)}
. This is because for a generator
g
∈
G
{\displaystyle g\in G}
, there exist integers
p
{\displaystyle p}
,
q
{\displaystyle q}
such that
P
=
g
p
{\displaystyle P=g^{p))
and
Q
=
g
q
{\displaystyle Q=g^{q))
. Therefore
e
(
P
,
Q
)
=
e
(
g
p
,
g
q
)
=
e
(
g
,
g
)
p
q
=
e
(
g
q
,
g
p
)
=
e
(
Q
,
P
)
{\displaystyle e(P,Q)=e(g^{p},g^{q})=e(g,g)^{pq}=e(g^{q},g^{p})=e(Q,P)}
.
The Weil pairing is an important concept in elliptic curve cryptography ; e.g., it may be used to attack certain elliptic curves (see MOV attack ). It and other pairings have been used to develop identity-based encryption schemes.
Slightly different usages of the notion of pairing [ edit ] Scalar products on complex vector spaces are sometimes called pairings, although they are not bilinear.
For example, in representation theory , one has a scalar product on the characters of complex representations of a finite group which is frequently called character pairing .
^ Hardie K.A.1; Vermeulen J.J.C.; Witbooi P.J., A nontrivial pairing of finite T0 spaces, Topology and its Applications, Volume 125, Number 3, 20 November 2002 , pp. 533–542.
^ Dan Boneh, Matthew K. Franklin, Identity-Based Encryption from the Weil Pairing , SIAM J. of Computing, Vol. 32, No. 3, pp. 586–615, 2003.