# Ideal Class Groups for VDF

## Class groups for primitive quadratic forms and imaginary quadratics fields (after M Bhargava).

In the context of [VDF's](https://hackmd.io/@tALDXbNWSVKr8RMQbHVAiw/rky6Ei4aO), the usual RSA group are replaced with a much scarier beast, the [`ideal class group of a quadratic number field`](https://en.wikipedia.org/wiki/Ideal_class_group). This is an attempt to review and implement this without using too fancy lingo. Note that this is rather central stuff in mathematics, it was invented by Gauss in the 19th century, improved by his student Dedekind and then by Manjul Bhargava (who got a Fields medal for it). Also one can quite convincingly argue that Dedekind's approach gave birth to modern abstract algebra.

I also have a POC implementation [here](https://gitlab.com/corneliuhoffman/ocaml_ideal_class-group).

The references are:
[the original paper](https://annals.math.princeton.edu/wp-content/uploads/annals-v159-n1-p03.pdf) and [an overview paper](http://www.crm.umontreal.ca/sms/2014/pdf/granville1.pdf).

For the following we will fix an integer $D$ so that $D<0$ and $D \equiv 1\pmod 4$ and $D$ is square free or $D \equiv 0\pmod 4$ and $\frac D 4$ is square free. Most uses are in the first case. We now consiedr the set
$$S = \{(a, b, c)\mid a>0, \ \gcd(a, b,c) =1 \mbox{ and } b^2 - 4ac = D\}.$$

In fact the triplet $(a, b, c)$ represents a `primitive quadratic form` $q(x,y) = ax^2+b xy +c y^2$. We say that $b^2-4ac$ is the discriminant of $(a,b,c)$.

Moreover we will introduce an equivalence relation on $S$ as follows: For any $M= \left(\begin{array}{cc}\alpha & \beta\\ \gamma & \delta\end{array}\right) \in SL_2(\mathbb{Z})$ that is $\alpha, \beta, \gamma, \delta$ are integers and $\alpha\delta - \beta\gamma = 1$, we consider the change of variables $x = \alpha u + \beta v; y = \gamma u + \delta v$ and we rewrite
$ax^2+b xy +c y^2 = Au^2 + Buv + Cv^2$, that is
$$(A, B, C) = (a\alpha^2 + b\alpha\gamma + c \gamma^2, 2a\alpha\beta+b(\alpha\delta + \beta\gamma)+ 2c\gamma\delta, a\beta^2+b \beta\delta +c\delta^2).$$

We then say that $(a, b,c)\cong (A,B,C)$. Note that $(a, b,c)$ and $(A,B,C)$ have the same discriminant.

A triplet $(a,b,c)$ is called `reduced` if
$$-a< b \le a \le c \mbox{ and if } a=c \text{ then } b\ge 0.$$

#### Lemma
Any pair equivalence class in $S$ contains a unique reduced triplet and there is an algorithm to compute it.

The algorithm is as follows:

1. There exists $-a < b' \le a$ so that $b' = b-2ka$ for some integer k. Then the matrix $\left(\begin{array}{cc}1& -k\\ 0 & 1\end{array}\right)$ transforms $(a, b,c)$ into a triplet $(a, b',c')$.

2. If $a>c$ or $a = c$ and $b < 0$ then the matrix
$\left(\begin{array}{cc}0 & -1 \\ 1 & 0 \end{array}\right)$ transforms $(a, b,c)$ into a triplet $(c, -b, a)$.

3. Repeat

Finally we define an operation on the set of equivalence classes of triplets as follows.

1. consider the labeled cube bellow.


If you imagine it as being a $2 \times 2 \times 2$ Rubik cube, ther are 3 possible moves each splitting the labels into two pieces. They are:

$$P_1 =\{a, b, c, d\} \cup \{e, f, g, h\}$$
$$P_2 = \{a, c, e, g\} \cup \{b, d,f, h\}$$
$$P_3 = \{a, e, b, f\} \cup \{c, g, d, h\}$$.

Note the order of the labels. Theyare obtained by always rtotating the cube until the label `a` is in top left.
To each such partiction associate a pair of matrices

$$ P_1 \rightarrow M_1 = \left(\begin{array}{cc}a & b\\ c & d\end{array}\right), N_1 = \left(\begin{array}{cc}e & f\\ g & h \end{array}\right)$$
$$ P_2 \rightarrow M_2 = \left(\begin{array}{cc}a & c\\ e & g\end{array}\right), N_2 = \left(\begin{array}{cc}b & d \\f & h \end{array}\right)$$

$$ P_3 \rightarrow M_3 = \left(\begin{array}{cc}a & e \\ b & f\end{array}\right), N_3 = \left(\begin{array}{cc}c & g\\ d & h \end{array}\right).$$

We now construct the three forms

$$f_i(x,y) = -\det (M_i x + N_i y).$$

so, for example:
$$f_1(x,y) = - det \left(\begin{array}{cc}ax+ey & bx + f y\\ cx + g y & dx + h y\end{array}\right) = - (ax+ey)(dx + h y) + (bx + f y)(cx + g y)= \\
= (bc-ad)x^2+(bg+fc-ah-ed)xy +(fg-eh)y^2 $$

Similarly
$$f_2(x,y) = (ce-ag)x^2+(de+cf-ah-bg)xy+(df-bh)y^2$$

and

$$f_3(x,y)= (eb-af)x^2 + (de+bg-cf-ah)xy+(dg-ch)y^2$$

Much like for eliptic curves, we will define an operation $\oplus$ on the equivalence classes in $S$ so that:$f_1\oplus f_2\oplus f_2= 0$.

* The identity for this operation is $(1,-1,\frac{1-D}4)=(1,1,\frac{1-D}4)$ if $D\equiv 1 \pmod 4$ and $(1,0,\frac D4)$ if $D\equiv 0 \pmod4$.
* The inverse of $(A,B,C)$ is $(A,B,C)$.

Therefore in order to multiply two forms

$(A_1, B_1, C_1)$ and $(B_2, B_2, C_2)$ then we need to find $a,\cdots h$ so that in the calculations above, $f_1=(A_1, B_1, C_1)$ and $f_2=(A_2, B_2, C_2)$. We then compute $f3 = (A_3, B_3, C_3)$ and get

$$(A_1, B_1, C_1)\oplus(A_2, B_2, C_2) \cong (A_3, -B_3, C_3).$$

It is usually better to also reduce the result of the computation.

SO how do we find $a, \cdots h$? There are obviously amny choices for them, each giving equvalent forms. Here is one solution.

1. Pick
$$a = \gcd(A_1,A_2,\frac{B_1+B_2}{2}), c = 0, d =-\frac{A_1}a, g = -\frac{A_2}a, h = -\frac{B_1+B_2}{2a}$$

We are left to pick $b, e,f$. The conditions are:

$$(fg-eh)=C_1, (df-bh) = C_2, (bg-ed) = \frac{B_1-B_2}2$$

Note that three relations are linearly dependent.

We will observe that, since d, g, h are now relatively prime, there exist integers $X,Y,Z$ so that $$Xd+Yg+Zh=1$$
$$B_1^2-4A_1C_1= B_2^2- 4A_2C_2 \Rightarrow \frac{B_1-B_2}2h=dC_1-gC_2.$$
To find these integers we can use the Euclidean algorithm for $A_1$ and $A_2$ and then again for $\gcd(A_1, A_2)$ and $\frac{B_1+B_2}2$.

If we multiply the first relation with $C_1$ ande use the second we get
$$C_1 =XdC_1+YgC_1+ZhC_1\\= X(\frac{B_1-B_2}2h+gC_2)+YgC_1+ZhC_1\\
=(XC_2+YC_1)g+(X\frac{B_1-B_2}2+ZC_1)h $$

similarly if we multiply with C_2 we get

$$C_2 =XdC_2+YgC_2+ZhC_2\\=XdC_2+ Y(dC_1-\frac{B_1-B_2}2h)+ZhC_2\\
=(XC_2+YC_1)d +(ZC_2-Y\frac{B_1-B_2}2)h $$

and finally multiplying by $\frac{B_1-B_2}2$ we get
$$\frac{B_1-B_2}2 = Xd\frac{B_1-B_2}2+Yg\frac{B_1-B_2}2+Zh\frac{B_1-B_2}2\\
=Xd\frac{B_1-B_2}2+Yg\frac{B_1-B_2}2+Z(dC_1-gC_2)\\
=(Y\frac{B_1-B_2}2-ZC_2)g +(X\frac{B_1-B_2}2+ZC_1)d $$

We now imediately note that a solution is given by:
$$f=(XC_2+YC_1); b= (ZC_2-Y\frac{B_1-B_2}2); e= -(X\frac{B_1-B_2}2+ZC_1)$$ and so

$$A_3=(eb-af)=-(ZC_2-Y\frac{B_1-B_2}2)(X\frac{B_1-B_2}2+ZC_1)- a(XC_2+YC_1)$$
$$B_3=de+bg-cf-ah \\ =\frac{A_1}{a}(X\frac{B_1-B_2}2+ZC_1)-\frac{A_2}{a} (ZC_2-Y\frac{B_1-B_2}2) + \frac{B_1+B_2}2$$

$$C_3 =(dg-ch)= \frac{A_1A_2}{a^2}$$