模算術線性同餘的小解

讓 $ p $ 是一個素數 $ N $ 位，讓 $ a,b,c $ 成為常數。問題是找到等效的解決方案 $ a x + b y \equiv c \pmod p $ 兩者都最多 $ N/2 $ 位。

有哪些算法可以解決這個問題？它有任何已知的硬度降低嗎？

您可以使用晶格縮減來解決此問題。

選擇一個大常數 $ S\in\mathbb Z $ 並考慮由以下矩陣的行​​跨越的格子： $$ L = \begin{pmatrix} S a & -1 & 0 & 0 \ S b & 0 & -1 & 0 \ S c & 0 & 0 & S \ S p & 0 & 0 & 0 \ \end{pmatrix} $$

現在要注意的關鍵是一些對 $ (x,y)\in\mathbb Z^2 $ 是模方程的​​解當且僅當 $ (0,x,y,S) $ 是這個格子中的一個向量。

此外，一些形式的向量 $ \vec v=(Sz,x,y,\pm S) $ 必須是短基的一部分，因為 $ \begin{pmatrix}S c & 0 & 0 & S\end{pmatrix} $ 是唯一的一行 $ L $ 在最後一列中非零。由於比例因子大 $ S $ 在第一列中，向量 $ \vec v $ 實際上會滿足 $ z=0 $ ，因此您可以通過計算的簡化基找到一個簡短的解決方案 $ L $ .

這是證明這一點的聖人記錄：

sage: p = next_prime(2**32)
sage: N = 1+floor(log(p,2)) # bit length
sage: S = 10**N
sage: a, b, c = randrange(p), randrange(p), randrange(p)
sage: a, b, c
(2206104035, 3690588304, 373686466)
sage: L = matrix(ZZ, [[S*a,-1,0,0], [S*b,0,-1,0], [S*c,0,0,S], [S*p,0,0,0]])
sage: L
[22061040350000000000                   -1                    0                    0]
[36905883040000000000                    0                   -1                    0]
[ 3736864660000000000                    0                    0          10000000000]
[42949673110000000000                    0                    0                    0]
sage: L.LLL()
[           0        49124        -7835            0]
[           0       -31049       -82479            0]
[-10000000000         2330       -37438            0]
[           0         4276       -42601  10000000000]
sage: (4276*a -42601*b) % p == c
True

引用自：https://crypto.stackexchange.com/questions/70693