\documentclass{article}
\usepackage{bbm}
\title{Stuff}
\author{Rik Snel}
\usepackage{pstricks}
\usepackage{pst-plot}
\usepackage{fp}
\usepackage{a4wide}
\input{vec2d}
\parindent0pt
\parskip .5ex
\begin{document}
\maketitle
\section{Elliptic curve group on $\mathbbm{R}$}

\subsection{Group theory}

An abelian group is a set S with a binary operator $+: S\times S \to S$, which
we will call the sum, that satisfies the following laws.

\begin{description}
	\item[associativity] For each $A, B, C \in S$ we have $(A + B) + C = A + (B + C)$.
	\item[unit] For each $A \in S$ there is an element $0 \in S$ such that $A + 0 = A$ and $0 + A = A$.
	\item[inverse] For each $A \in S$ there is an element $B \in S$ such that $A + B = B + A = 0$.
	\item[commutativity] For any $A, B \in S$ we have $A + B = B + A$
\end{description}

Mathematicians have studied the consequences of these laws for more than 2
centuries; lots of useful properties can be proven, just by starting from these
laws.

For example: assume $0, 0' \in S$ satisfy the \textbf{unit} law. Then we have $0
= 0 + 0' = 0'$, so the unit element is uniquely determined. And, as a bonus, it
makes sense to use it in the \textbf{inverse} law as if it is a unique element.
It can be shown that the \textbf{inverse} of an element is also uniquely
determined.

A result of the \textbf{associativity} law is that an expression like $A + B +
C$ can be written unambiguously, because it does not matter if $A + B$ or $B +
C$ is calculated first.

The number of elements in the set is called the \textbf{order} of the group. If
there is a $G \in S$ such that every element of $S$ can be written as 
\[
	\underbrace{G + G + \cdots + G}_a
\] for some value of $a$, then $G$ is called a $\textbf{generator}$ of the group.
In the following we will use $aG$ as a short form of this repeated addition.

An example of an infinite group is $\mathbbm{Z}$; the set of integers with
addition as the group operator.

There are also finite groups, for $\mathbbm{F}_p = \{0, 1, 2, \ldots, p - 1\}$
where $p$ is a prime number. This is a group under addition using normal
addition, with the stipulation that if the result is outside of the range from
$0$ to $p-1$, a multiple $p$ is added or subtracted to get it in range. If we
have $p = 5$ then $4 + 3 = 2$.

If we disregard $0$, this set forms also a group under ordinary multiplication
(with the same stipulation). Every element besides $0$ has an inverse. The proof
uses the fact that gcd of those numbers and $p$ is $1$.  Furthermore the
\textbf{distributive} law holds; for any $a, b, c \in \mathbbm{F}_p$ we have
$a(b + c) = ab + ac$.

A group that works like $\mathbbm{F}_p$ is called a \textbf{field}.
The real numbers, $\mathbbm{R}$ also
form a \textbf{field}. $\mathbbm{F}_p$ will play an important role in this article.

\subsection{Elliptic curve intuition}

By choosing an appropriate coordinate system any third degree polynomal can be
written with $1$ as leading coefficient and no quadratic term, so without loss
of generality the Weierstrass form of an elliptic curve is
\[
	y^2 = x^3 + cx+d,
\]

Let $S$ be the set of all points on the curve and an extra element which we wil call $\infty_0$, formally
\[
	S = \{ (x, y) | y^2 = x^3 + c x + d\} \cup \{ \infty_0 \}.
\]
The subscript on $\infty_0$ will be explained in due course. In this section we assume that $x, y\in \mathbbm{R}$

We define a group operation for any $A, B \in S$ as follows (take the first condition that applies):
\begin{description}
	\item[if $A = \infty_0 \wedge B = \infty_0$:] the result is $\infty_0$
	\item[if $A = \infty_0 \vee B = \infty_0$:] the result is the one that's not $\infty_0$
	\item[if $x_A \not= x_B$:] mirror the third intersection of the line through $A$ and $B$ and the curve in the $x$-axis
	\item[if $y_A = y_B \not= 0$:] mirror the other intersection of the tangent line at $A$ and the curve in the $x$-axis
	\item[in all other cases:] the result is just $\infty_0$
\end{description}

See the drawing below for an illustration of these rules. The point $\infty_0$
is thought to live all the way up/down. We start with point
$A$, and we determine $A + A$ by drawing the tangent line $l$ to the curve in
$A$, and labeling the other intersection with the curve $B'$, then we mirror
$B'$ in the $x$-axis and we get $B$, so $2A = B$. Then, to add $A$ and $B$, we
draw line $m$ through $A$ and $B$, find the other intersection with the curve,
label it $C'$ and mirror it in the $x$-axis to get $C$. So $A + B = C$. And also
$3A = C$. Furthermore we see that $B + B' = C + C' = \infty_0$; the inverse of a point can be
gotten by mirroring it in the $x$-axis.

\VDDdef O(0,0)K(-2,-4)L(3,4)X(1,0)Y(0,1)
\VDDdcanvas 1:1
  \VDDdeflinepoint x:OX
  \VDDdeflinepoint y:OY
  \VDDdwholeline xy
  %\VDDdruitjes
  \FPset\xA{1.7}
  \FPupn\yA{2 xA copy copy mul mul 7 add root}
  \FPupn\dirA{3 xA xA mul mul 2 yA mul div}
  \FPadd\xAdir{\xA}{1}
  \FPupn\xB{dirA dirA mul xA sub xA sub}
  \message{\xB}%
  \FPupn\yB{2 xB copy copy mul mul 7 add root}
  \FPupn\dirAB{yA yB sub xA xB sub div}
  \FPupn\xC{dirAB dirAB mul xA sub xB sub}
  \FPupn\yC{2 xC copy copy mul mul 7 add root}
  \FPadd\yAdir{\yA}{\dirA}
  \FPneg{\yBp}{\yB}
  \FPupn\dirBp{3 xB xB mul mul 2 yBp mul div}
  \FPadd\xBpdir{\xB}{1}
  \FPadd\yBpdir{\yBp}{\dirBp}
  \FPupn\dirC{3 xC xC mul mul 2 yC neg mul div}
  \FPneg{\dirCp}{\dirC}
  \FPadd\xCdir{\xC}{1}
  \FPadd\yCdir{-\yC}{\dirC}
  \FPadd\xCpdir{\xC}{1}
  \FPadd\yCpdir{\yC}{\dirCp}
  \message{\dirC}
  \VDDdef A(\xA,\yA)A'(\xAdir,\yAdir)B(\xB,\yB)B'(\xB,\yBp)C(\xC,-\yC)C'(\xC,\yC)B''(\xBpdir,\yBpdir)C''(\xCdir,\yCdir)C'''(\xCpdir,\yCpdir)
  \VDDdeflinepoint l:AA'
  \VDDdeflinepoint k:BB'
  \VDDdeflinepoint o:B'B''
  \VDDdeflinepoint p:CC''
  \VDDdeflinepoint q:C'C'''
  \VDDdeflinepoint n:CC'
  \VDDdeflinepoint m:AB
  \VDDdwholeline lm
  \VDDdhiddenstyle
  \VDDdwholeline kn
  \VDDdvisiblestyle
  \VDDdpoint ABCB'C'
  \VDDllineedgeletter y:L:-1:1
  \VDDllineedgeletter x:L:1:1
  \VDDllineedgeletter l:L:1:-1
  \VDDllineedgeletter m:L:1:-1
  \VDDllinelinepointletter lm:AL:1:1
  \VDDllinelinepointletter ko:B'L:1:1
  \VDDllinelinepointletter lk:BL:1:1
  \VDDllinelinepointletter xy:OL:1:1
  \VDDllinelinepointletter pn:CL:1:1
  \VDDllinelinepointletter qn:C'L:-1:1
  \VDDmessage A
  \parametricplot[plotpoints=300]{-5}{5}{t t t mul -7 add dup dup abs 1 3 div exp exch div abs mul t}
\VDDdcanvasend

This looks nice and all, but it raises some questions. Is there always a third
intersection in the first case? Is there always an `other' intersection in the
second case? Can there be more than three intersections? Do these rules actually
satisfy the group laws?

\subsection{A brief foray into cubic equations}

The general monic (this means that the coefficient of $x^3$ is $1$) cubic equation is 
\[
	x^3 + ax^2+ bx + c = 0.
\]
If the roots $p$, $q$, $r$, are known, then the equation can be written as
\[
	(x-p)(x-q)(x-r) = 0.
\]
If $p$, $q$ and $r$ are equal, then it is a root with multiplicity $3$. If, in
contrast, two of them are equal, then there is one root with multiplicity $2$
and one with multiplicity $1$. If they all are different, then there are three
roots with multiplicity $1$.

After expanding the second form, we get
\[
	x^3 - (p + q + r)x^2 + (pq + pr + qr)x - pqr = 0,
\]
therefore $r = -a - p - q$. So if we have two roots $\in \mathbbm{R}$, we have a
third, and it can be found in this very simple way.


\subsection{Formulas for point addition}

Let's take $y = ax + b$, the general non-vertical line, and examine the resulting equation
\[
	(ax+b)^2 = x^3 + cx + d.
\]
Expanding the square and rearranging the terms give
\[
	x^3 - a^2x^2 + (c - 2ab)x + d - b^2 = 0,
\]
This equation can be written in terms of it's roots $x_A$, $x_B$ and $x_C$:
\[
	(x - x_A)(x-x_B)(x-x_C) = 0.
\]
From this, it follows that $x_C = a^2 - x_A - x_B$.

Let $A$ and $B$ be points that lie on the curve. First assume that $x_A \not= x_B$.
\[
	y = \frac{y_B - y_A}{x_B - x_A} x + \frac{x_By_A - x_Ay_B}{x_B-x_A}.
\]
Since $x_A$ and $x_B$ are roots of the aforementioned equation, there is a point $C$ on the curve of which the $x$-co\"ordinate is also a root of this equation, namely
\[
	x_C = \left(\frac{y_B - y_A}{x_B - x_A}\right)^2 - x_A - x_B.
\]
The $y$-co\"ordinate can also be calculated
\[
	y_C =\frac{y_B - y_A}{x_B - x_A} x_C + \frac{x_By_A - x_Ay_B}{x_B-x_A}. 
\]
Note that the parameters of the curve, $c$ and $d$, do not enter explicitly in these equations.

Now, let's assume that $A$ and $B$ are the same point and $y_A \not= 0$. In this case we can take the tangent line in these points and find the third point. In this case, $a$ must be calculated
using the derivative of the curve
\[
	2y\mathrm{d}y = (3x^2 + c)\mathrm{d}x.
\]
which gives
\[
	a = \frac{\mathrm{d} y}{\mathrm{d} x} = \frac{3x_A^2+c}{2y_A}.
\]
The formula for the tangent line through $A$ is
\[
	y = \frac{3x_A^2+c}{2y_A} (x - x_A) + y_A.
\]
\section{Prime fields}
Let $p$ be an odd prime number and take the integers modulo $p$
\[
	\mathbbm{F}_p = \left\{-\frac12(p-1), \ldots, -2, -1, 0, 1, 2, \ldots, \frac12(p-1)\right\}
\]
With these numbers, we can do addition, subtraction, multiplication and division as usual. Take for example $\mathbbm{F}_{11}$. In $\mathbbm{F}_{11}$ we have
$-5 + 3 = -2$, $-2 - 3 = -5$, $-5\cdot 3 = -4$ and $5:3 = -2$.


\section{Commitments}
\subsection{Hiding}
\subsection{Binding}
\section{Pedersen commitments}
\section{Arguments of knowledge}
\subsection{Completeness}
\subsection{Soundness}
\subsection{Zero knowledgeness}
\end{document}
