算法找到一個equidistributed溶液到線性同餘系統

Question

我面對在密碼學應用以下的問題：我已給定一組線性同餘

a[1]*x[1]+a[2]*x[2]+a[3]*x[3] == d[1] (mod p) 
b[1]*x[1]+b[2]*x[2]+b[3]*x[3] == d[2] (mod p) 
c[1]*x[1]+c[2]*x[2]+c[3]*x[3] == d[3] (mod p) 

這裏，x是未知的A，B，C ，d給出

該系統很可能欠定，所以我有一個很大的解決方案空間。我需要一種算法，使用僞隨機數生成器（或失敗）找到等分佈的解決方案（即解空間中的等距分佈）。

大多數標準算法求解線性方程組的系統，我從我的線性代數課知道是不是直接適用於儘可能我可以看到同餘...

我現在，「安全」的算法如下所示：找到所有隻出現在一個方程中的變量，並分配一個隨機值。現在如果在每一行中只有一個變量是未分配的，則根據一致性分配值。否則失敗。

任何人都可以給我一個線索如何解決這個問題一般？

Answer 1

就像你在線性代數課程中學到的一樣，你可以使用高斯消元法和類似的算法，但是所有的算術都是用mod p（p是一個素數）來執行的。一個重要的區別是在「分割」的定義中：計算a/b而不是計算a *（1/b）（單詞中的「a b times inverse」）。請看下面的更改通常使用的數學運算

• 加法：A + B成爲A + B模p
• 減法：AB成爲AB模p
• 乘法：A * B成爲A * B模p
• 除法：A/b變成：如果p除以b，則 「錯誤：除以零」，否則爲A *（1/b）模p

爲了計算b模p的逆你可以使用擴展的歐幾里德算法或者計算b **（p-2）mod p。

而不是試圖自己滾動它，尋找一個現有的庫或包。我認爲也許Sage可以做到這一點，當然還有Mathematica和Maple以及類似的商業數學工具。