因子基方法分解整数

已知73/3和97/4是Sqrt[589]的两个最佳逼近
收集了一些方程 mod589下有
20^2 = -189
22^2 = -105
23^2 = -60
24^2 = -13
26^2 = 87
27^2 =140
可以利用因子基方法给出589的分解

a = {20, 22, 23, 24,26,27}
b = {-189, -105, -60, -13,-87,140}

上图里的矩阵，每一行是对b里的数的分解结果，每一行，括号里第一个是因子，第二个是指数。

因子基的上界应该取7
而-13这个13的因子，其他的数没有，故-13所在这个方程抛掉。
同理，-87有29的因子，其他数没有，故-87所在的方程也抛掉。

于是
a = {20, 22, 23, 27}
b = {-189, -105, -60, 140}

关于系数可以列方程
yi表示第i个方程的选取，若为0，则该方程不选，否则为选。
所以有等式
1.对-1：y1+y2+y3=偶
2.对2：2y3+2y4=偶
3.对3：3y1+y2+y3=偶
4.对5：y2+y3+y4=偶
5.对7：y1+y2+y4=偶

2式自然成立
4式-5式，知y1和y3奇偶性相同
由1式，知y2只能为偶数，故y2=0
从而由4式知，y4与y3奇偶性相同
故可以给出一组解为
(y1,y2,y3,y4)=(1,0,1,1)

a = {20, 22, 23, 27}
b = {-189, -105, -60, 140}
x=20×23×27 mod 589=51
y=Sqrt[(-189)×(-60)×140] mod 589=82
GCD(y-x,n)=31