LLLは与えられた格子の基底から，その格子の中で大きさが小さい格子点を求める．

• 線形の方程式を建てる
• 小さい格子点が解になるように大きい基底を考える

Cake CTF 2022 rock door

https://qiita.com/kusano_k/items/97684e8324a973f95116#rock-door-lunatic-crypto

kが求まるとxを求めることができる．

mod qが1024bitなのに対して，kが256bit程度．

1列目はk * 2**256

2列目はz + xr

3列目が0になるベクトルが解の候補

2**2048とかはうまいこと調整する．

M = [
  [2**256, 0, s*2**2048],
  [0,      1, 1*2**2048],
  [0,      0, q*2**2048],
]

M = Matrix(M).LLL()