1\documentclass{article}
  2\usepackage[utf8]{inputenc}
  3\usepackage{amsfonts}
  4\usepackage{amsthm}
  5\usepackage{amsmath}
  6\usepackage{amssymb}
  7\usepackage{enumerate}
  8\usepackage{hyperref}
  9\hypersetup{
 10    colorlinks,
 11    citecolor=black,
 12    filecolor=black,
 13    linkcolor=black,
 14    urlcolor=blue
 15}
 16% \usepackage{xcolor}
 17
 18% prevent warnings of underfull \hbox:
 19% \usepackage{etoolbox}
 20% \apptocmd{\sloppy}{\hbadness 4000\relax}{}{}
 21
 22\theoremstyle{definition}
 23\newtheorem{definition}{Def}[section]
 24\newtheorem{theorem}[definition]{Thm}
 25\newtheorem{innersolution}{}
 26\newenvironment{solution}[1]
 27{\renewcommand\theinnersolution{#1}\innersolution}
 28{\endinnersolution}
 29
 30
 31\title{Bilinear Pairings - study}
 32\author{arnaucube}
 33\date{August 2022}
 34
 35\begin{document}
 36
 37\maketitle
 38
 39\begin{abstract}
 40  Notes taken from \href{https://sites.google.com/site/matanprasma/artifact}{Matan Prsma} math seminars and also while reading about Bilinear Pairings. Usually while reading papers and books I take handwritten notes, this document contains some of them re-written to $LaTeX$.
 41
 42	The notes are not complete, don't include all the steps neither all the proofs. I use these notes to revisit the concepts after some time of reading the topic.
 43\end{abstract}
 44
 45\tableofcontents
 46
 47\section{Weil reciprocity}
 48
 49\section{Generic Weil Pairing}
 50
 51\begin{definition}{Divisor}
 52  $$D= \sum_{P \in E(\mathbb{K})} n_p \cdot [P]$$
 53\end{definition}
 54
 55\begin{definition}{Degree \& Sum}
 56  $$deg(D)= \sum_{P \in E(\mathbb{K})} n_p$$
 57  $$sum(D)= \sum_{P \in E(\mathbb{K})} n_p \cdot P$$
 58\end{definition}
 59
 60\begin{definition}{Principal divisor}
 61  iff $deg(D)=0$ and $sum(D)=0$
 62\end{definition}
 63$D \sim D'$ iff $D - D'$ is principal.
 64
 65
 66\begin{definition}{Evaluation of a rational function}
 67  $$r(D)= \prod r(P)^{n_p}$$
 68\end{definition}
 69
 70\subsection{Generic Weil Pairing}
 71Let $E(\mathbb{K})$, with $\mathbb{K}$ of char $p$, $n$ s.t. $p \nmid n$.
 72
 73$\mathbb{K}$ large enough: $E(\mathbb{K})[n] = E(\mathbb{\overline{K}}) = \mathbb{Z}_n \oplus \mathbb{Z}_n$ (with $n^2$ elements).
 74
 75$P, Q \in E[n]$:
 76$$D_P \sim [P] - [0]$$
 77$$D_Q \sim [Q] - [0]$$
 78We need them to have disjoint support:
 79$$D_P \sim [P] - [0]$$
 80$$D_Q \sim [Q+T] - [T]$$
 81
 82$$\Delta D = D_Q - D_Q' = [Q] - [0] - [Q+T] + [T]$$
 83
 84
 85\section{Exercises}
 86\emph{An Introduction to Mathematical Cryptography, 2nd Edition} - Section 6.8. Bilinear pairings on elliptic curves
 87
 88\begin{solution}{6.29}
 89  $div(R(x) \cdot S(x)) = div( R(x)) + div( S(x))$, where $R(x), S(x)$ are rational functions.
 90  \\proof:\\
 91  \emph{Norm} of $f$: $N_f = f \cdot \overline{f}$, and we know that $N_{fg} = N_f \cdot N_g~\forall~\mathbb{K}[E]$,\\
 92  then $$deg(f) = deg_x(N_f)$$\\
 93  and $$deg(f \cdot g) = deg(f) + deg(g)$$
 94
 95  Proof:
 96  $$deg(f \cdot g) = deg_x(N_{fg}) = deg_x(N_f \cdot N_g)$$
 97  $$= deg_x(N_f) + deg_x(N_g) = deg(f) + deg(g)$$
 98
 99  So, $\forall P \in E(\mathbb{K}),~ ord_P(rs) = ord_P(r) + ord_P(s)$.\\
100  As $div(r) = \sum_{P\in E(\mathbb{K})} ord_P(r)[P]$, $div(s) = \sum ord_P(s)[P]$.
101
102  So,
103  $$div(rs) = \sum ord_P(rs)[P]$$
104  $$= \sum ord_P(r)[P] + \sum ord_P(s)[P] = div(r) + div(s)$$
105\end{solution}
106
107\vspace{0.5cm}
108
109\begin{solution}{6.31}
110  $$e_m(P, Q) = e_m(Q, P)^{-1} \forall P, Q \in E[m]$$
111  Proof:
112  We know that $e_m(P, P) = 1$, so:
113  $$1 = e_m(P+Q, P+Q) = e_m(P, P) \cdot e_m(P, Q) \cdot e_m(Q, P) \cdot e_m(Q, Q)$$
114
115  and we know that $e_m(P, P) = 1$, then we have:
116  $$1 = e_m(P, Q) \cdot e_m(Q, P)$$
117  $$\Longrightarrow e_m(P, Q) = e_m(Q, P)^{-1}$$
118\end{solution}
119
120
121
122
123\end{document}