正定二元型约化

剪切整理倾斜，交换缩小首系数 ​

剪切不改变第一条格基方向，而是给第二条方向加上第一条的整数倍。中项因此以 $2a$ 为步长变化；选定的 $k$ 把它送入半开区间 $(-a,a]$。交换则让当前较短的第二条方向成为第一条，并用一个负号保持定向。

每次真正回到循环的交换都满足新首系数 $c<a$。它仍是正整数，因为正定型在 $(0,1)$ 的值为正。正整数不可能无限严格下降，所以算法终止。最后 $a=c,b<0$ 的交换不再开启循环，只用于选定边界的正号。

把三步计算连成一个证书 ​

对 $Q=(24,83,72)$，判别式为 ${83}^2-4\cdot 24\cdot 72=-23$。算法给出

总矩阵行列式为 $6-5=1$。读者可直接展开

约化型在 $(2,1)$ 表示 $13$，乘总矩阵得到原坐标 $(1,-1)$；回代 $24-83+72=13$，表示证书也被完整保存。

边界重号为什么必须处理 ​

$(1,-1,6)$ 和 $(1,1,6)$ 都满足 $|b|\le a\le c$，但前者经 $T_1$ 就变成后者。规则在 $|b|=a$ 时只保留 $b\ge 0$，消除这次重复。

另一种重复发生在 $a=c$：$(2,-1,2{)}^S=(2,1,2)$。两个型都在同一条圆弧边界上，故还必须规定 $a=c$ 时保留非负中项。这里的“圆弧”只是一种几何解释，算法与证明本身不需要复上半平面。

$D=-3$ 的 $(1,1,1)$ 和 $D=-4$ 的 $(1,0,1)$ 也在合同范围内。它们有较多保型换元，但都只输出一个约化三元组。不能为了避免对称性而把这些边界型排除。

正定性负责哪一步 ​

对不定型 $(1,0,-2)$，第二个系数方向的值 $c=-2$ 已不是正整数。“交换后首系数下降”无法构成正整数终止证明。Pell 方程中的无限对称性应使用不定型或周期连分数理路二次无理数的周期连分数Periodic continued fractions of quadratic irrationals · Lagrange periodic continued fraction theorem · 二次无理数的 Lagrange 周期定理以有界整数状态证明二次无理数的连分数最终周期，并为平方根建立无小数误差的周期计算与准确停止规则。的方法，本算法不接受这种输入。

也不能把矩阵 $\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$ 偷换成这里的 $S$。普通无符号交换行列式为 $-1$，会反转定向；正等价需要同时改变中项符号。

最小值定位所有可能的首列 ​

下面证明约化代表唯一，而不只证明算法停下来。对任何约化 $Q=(a,b,c)$ 和非零整数 $(x,y)$，有

最后一步来自

所以最小非零整数值恰为 $a$，由 $(\pm 1,0)$ 取得。逐项看等号，还得到全部最小向量：

• $a<c$ 时，仅有 $(\pm 1,0)$；
• $a=c$ 且 $0\le b<a$ 时，另有 $(0,\pm 1)$；
• $a=b=c$ 时，再增加 $(1,-1),(-1,1)$。

这张短表同时控制普通情形、方格对称和六角对称。

唯一性：等价矩阵的第一列没有自由选择 ​

设两个约化型 $Q,Q^{\prime }$ 正等价。它们表示相同整数，最小正值给出 $a^{\prime }=a$。若 $Q^{\prime }=Q^U$，$U$ 的第一列必须属于上面的最小向量表。

当第一列是 $(\epsilon ,0)$ 时，行列式条件迫使

于是 $b^{\prime }=b+2a\epsilon q$。两边都在 $(-a,a]$，只能有 $b^{\prime }=b$；再由相同判别式得到 $c^{\prime }=c$。这已经处理全部 $a<c$ 情形。

若 $a=c$、$0\le b<a$，剩下的可能首列是 $(0,\epsilon )$。此时

半开区间限制迫使 $s=0$，从而 $b^{\prime }=-b,c^{\prime }=a$。但 $a^{\prime }=c^{\prime }$ 的边界规则要求 $b^{\prime }\ge 0$，所以只有 $b=0$ 才能发生，仍得到同一个三元组。

最后考虑 $a=b=c$。矩阵

保持 $Q=a(x^2+xy+y^2)$，且 $R^j(1,0)$、$0\le j<6$ 正好列出六个最小向量。给定 $U$，取 $V=R^j$ 与它具有相同第一列，则 $V^{-1}U$ 的第一列为 $(1,0)$，且 $Q^U=Q^{V^{-1}U}$。问题回到第一种情况，仍只有 $Q^{\prime }=Q$。唯一性全部证完。

由判别式上界列尽所有类 ​

对约化型，

因此

逐个枚举 $a,b$，检查 $c$ 是整数、约化边界及所需的内容条件，便得到全部代表。存在性保证没有漏类，唯一性保证没有重类；两个部分缺一不可。

对 $D=-23$，只有 $a=1,2$。当 $a=1$，边界给 $b=1,c=6$；当 $a=2$，只有 $b=\pm 1,c=3$ 通过整除检查。全部代表恰为

三者各是不同正等价类。仅数出三个类尚未决定乘法，Gauss 合成理路Gauss 二元型合成Gauss composition of binary quadratic forms · Dirichlet composition · 二元二次型类合成在负基本判别式下构造互素首系数和共同中项，用整数CRT计算型类乘积；由定向理想双射证明选择无关与群律，并完整算出判别式−23的三阶类群。会给出这三个类的完整运算表。

计算成本与验证成本分别说清 ​

直接枚举的 $(a,b)$ 候选数为 $O(|D|)$；这是按判别式的数值计数，不能称为按输入位数的多项式枚举。类数本身也会随 $|D|$ 增长。

单个型的约化快得多。归一化后 $|b|\le a$，交换所得首系数为

若 $a\ge \sqrt{|D|}$，便有 $a_{\mathrm{new}}\le a/2$。进入 $a<\sqrt{|D|}$ 后，若还需交换，则至多再交换一次就能约化：当 $c\le \sqrt{|D|}/2$ 时，新的归一化型自动满足末系数不小于首系数；当 $c>\sqrt{|D|}/2$ 时，$|b|\le a<2c$，交换后的归一化至多补一次剪切，末系数为 $a$ 或 $a+c-|b|\ge c$。相等时再执行终止的符号规则即可。

所以从首系数 $a_0$ 开始，算术轮数为 $O(1+\log (a_0+1))$。每轮大整数除法及矩阵乘法的位成本另计。若只验证给出的结果，检查 $\det U=1$、三个系数的换元恒等式和约化边界便已足够；无需信任求解程序的内部路径。