novus log

這裡介紹一種方法，可從連續出現的數字序列，回推線性同餘函數的相關參數。先聲明一下，密碼學、亂數、數論並不是我的專長，只是最近看到有人問，碰巧我讀過而已，如果內容有錯漏歡迎指正。這裡介紹的只是通俗易記的做法，可能不是目前最好的方法。

線性同餘法是目前常見的偽亂數產生法之一，可以寫成：

x[n] = (a * x[n-1] + c) mod m

其中 a、c、m 為根據某些原則小心選定的常數，這裡不多介紹。假如我們取

• a = 11
• c = 5
• m = 31
• x[0] = 3

則得到一個週期31的序列：

7, 20, 8, 0, 5, 29, 14, 4, 18, 17, 6, 9,
11, 2, 27, 23, 10, 22, 30, 25, 1, 16, 26,
12, 13, 24, 21, 19, 28, 3, 7, ...

假如我們只知道其中片段連續數字，例如 7, 20, 8, 0, 5, 29, 14, 4，要如何推測接下來的數字呢？首先要得到 m，這並不容易，不過取前4個數字即可利用下面這個行列式可以求得 m 的整數倍 m* 。

| 7 20  1|
|20  8  1|
| 8  0  1|

這個行列式算出來的 m* = 248 = 31 * 8，確實符合我們一開始選擇的 m，但是現在我們假裝不知道 m 是多少。從 m* 猜測 m 有一些方法，首先 m 通常不會亂選，常見的選擇之一是梅森質數，或者為了速度起見選用2的次方。在這個例子裡 8 和 31 各自滿足一項條件，看一下數字範圍就知道不可能是 8，所以一定是31。

再者，假如我們得到的序列夠多，就可以利用上面的行列式求出多組 m* ，然後算一下 gcd 就八九不離十。這裡我們再取 5, 29, 14, 4，套用上面的行列式得到 465，算 gcd(248, 465) = 31。

有了 m 之後我們就可以解下列的方程組：

7a + c = 20 (mod 31)
20a + c = 8 (mod 31)
8a + c = 0 (mod 31)

細節就不多說了，總之可以兩兩相減把 c 都消掉，再把 a 求出來。如果只打算從 x[n-1] 預測 x[n]，求出 a 以後其實也沒有必要再求 c 了，直接用下面算式就可以

x[n] = (a*x[n-1] + x[1] - a*x[0]) (mod m)

舉例來說，我們取 0 和 5 當成首兩項，求 4 的下一個數：(11 * 4 + 5) mod 31 = 18，和前面完全吻合。

這裡只是線性同餘法最簡單的情形，實用的亂數產生器通常還會在輸出時做一些 bit shift/mask 等等修飾，因此從輸出結果逆推常數會困難很多。

延伸閱讀

上面方法已經有人寫成程式：www.reteam.org/papers/e59.pdf

以下這篇是比較正規的作法，而且可以套用到更廣義的多項式同餘：

Joan Boyar (1989). "Inferring sequences produced by pseudo-random number generators". Journal of the ACM 36 (1): 129–141. DOI:10.1145/58562.59305.

Marsaglia,G. (1968). Random Numbers fall mainly in the planes. Proceedings of the National Academy of Sciences,61,25-28