https://dexterjie.github.io/2023/07/29/%E6%A0%BC%E5%AF%86%E7%A0%81%E5%85%A5%E9%97%A8/

from Crypto.Util.number import *
from secret import flag
import gmpy2

# assert len(flag) == 47
#376bit
# flag=b'SICTF{xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx}'
# f = bytes_to_long(flag)
# p = getPrime(512)
# g = getPrime(128)
# h = gmpy2.invert(f, p) * g % p
# print('h =', h)
# print('p =', p)
'''
配平
g=fh+kp

'''
D=2**248
from Crypto.Util.number import *
from gmpy2 import *
h = 9848463356094730516607732957888686710609147955724620108704251779566910519170690198684628685762596232124613115691882688827918489297122319416081019121038443
p = 11403618200995593428747663693860532026261161211931726381922677499906885834766955987247477478421850280928508004160386000301268285541073474589048412962888947     
Ge = Matrix(ZZ,[[1,D*h],[0,D*p]])#
print(Ge.LLL())
f,g = Ge.LLL()[0]
f,g = abs(f),abs(g)//D
print(long_to_bytes(f))

LLL算法需要的是矩阵参数，最简单的矩阵如下 D属于任意整数
$$
\begin{bmatrix}
1 & D h \
0 & D q \
\end{bmatrix}
$$
其满足下列条件
$$
\begin{bmatrix} f & -k \end{bmatrix}
\begin{bmatrix}
1 & D h \
0 & D q \
\end{bmatrix}

\begin{bmatrix} f & D g \end{bmatrix}
$$

配平需要满足
$$
f \approx D \cdot g
$$

例如上面的f为376bit,g为128位,所以D为2^248 位数大致相同即可

基本形式

LLL算法需要的是矩阵参数，最简单的矩阵如下 D属于任意整数$$\begin{bmatrix} 1 & D h \ 0 & D q \\end{bmatrix}$$其满足下列条件$$\begin{bmatrix} f & -k \end{bmatrix}\begin{bmatrix} 1 & D h \ 0 & D q \\end{bmatrix}

LLL算法需要的是矩阵参数，最简单的矩阵如下 D属于任意整数
$$
\begin{bmatrix}
1 & D h \
0 & D q \
\end{bmatrix}
$$
其满足下列条件
$$
\begin{bmatrix} f & -k \end{bmatrix}
\begin{bmatrix}
1 & D h \
0 & D q \
\end{bmatrix}