雙變數模線性方程的小根？

假設我在兩個變數之間有一個簡單的仿射關係 $ x $ 和 $ y $ 在一個領域 $ \mathbb{F}_p $ ( $ p $ 是一個很大的安全參數）： $ ax + by + c = 0 $

什麼算法適合找到所有根 $ (x,y) $ 這樣 $ x < X $ 和 $ y < Y $ 對於一些小 $ X, Y $ 相比 $ p $ ?

我發現的每個算法似乎都過大了，處理多個方程、更高階或更多變數的系統。銅匠方法仍然是這裡最好的嗎？LLL 可用於查找一個根，但我不知道如何找到其他根。

此類方程的所有解 $ \mathbb{Z} $ 是形式 $ x=x_0-\frac{ka}{gcd(a,b)}, y=y_0+\frac{kb}{gcd(a,b)} $ 為了 $ k\in \mathbb{Z} $ ， 在哪裡 $ (x_0,y_0) $ 是任何解決方案。

看看這些數字模 $ p $ 您將獲得方程組解的參數化。這可能會幫助您找到一些小的解決方案，具體取決於參數的大小 $ X,Y $ .

現在，請注意等式

$$ ax+by=c+p $$也會給出解決方案（或更換 $ p $ 由任何 $ \theta p $ 為了 $ \theta\in \mathbb{Z} $ )，因為在 $ \mathbb{F}_p $ ，等式相同。我會讓你想想解決方案是否相同。

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