Monday, January 28, 2019

Factoring using BQF (not SQUFOF)

We start with a very brief primer to Binary Quadratic Forms (BQF). For more information ⦗1⦘ is a very good source to start with.

 A Binary Quadratic Form is a polynom of the form $Q(x,y) = ax^2+bxy+cy^2$ with integer coefficients. We focus on integer BQF, i.e., $x,y \in \mathbb{Z}$. Often one is only interested in the behaviour of the coefficients $a,b,c$ and in those cases one refers to a BQF simply by the triple $(a,b,c)$. Further, the integer $D$ defined as: $$D = b^2 - 4ac$$ is called the discriminant of $(a,b,c)$.

 A positive definite BQF $(a,b,c)$, i.e. $D < 0, a > 0$, is reduced if $-a < b < a < c$. Gauss observed, that all reduced BQF with the same discriminant form an abelian group and he gave a composition algorithm for those group elements. This group is called the class group and is usually denoted as $\mathcal{Cl}(D)$. The size of the group has a special name and is called the class number $h(D)$. Informally spoken, the class group $\mathcal{Cl}(D)$ contains all different reduced quadratic forms with the same discriminant $D$.