破解線性同餘生成器，按順序知道每隔一個單詞

我需要破解線性同餘生成器的範例之一。

我有 $ X_{n+1} = (a \cdot X_n + b) \bmod m $

我知道輸出序列中的所有其他單詞：

…, 3158, …, 1888, …, 1285, …, 1744, …, 253, …, 722, …

問題是如何獲取生成器參數（ $ a $ , $ b $ , $ m $ ) ? 我已經閱讀了破解線性同餘生成器 ，但仍然不知道如何破解它。

有時，與其做酷數學，最簡單的方法是蠻力！

#include <stdio.h>
#include <assert.h>

int main()
{
   enum { X0 = 3158, X1 = 1888, X2 = 1285, X3 = 1744, X4 = 253, X5 = 722,
          M_START = 3159 };
   for (int m = M_START; m < 10*M_START; ++m) {
       for (int a = 2; a < m; ++a)  {
           int c = X2 - ((X1 * a) % m);
           if (c < 0)
               c += m;
           int my_x2 = (X1 * a + c) % m;
           assert(my_x2 == X2);
           int my_x3 = (X2 * a + c) % m;
           int my_x4 = (X3 * a + c) % m;
           int my_x5 = (X4 * a + c) % m;
           if (my_x3 == X3 && my_x4 == X4 && my_x5 == X5) {
               printf ("m=%d, a=%d, c=%d\n", m, a, c);
           }
       }
   }

   return 0;
}

此程式碼進行了詳盡的搜尋。不到一秒鐘，它吐出：

m=3187, a=2663, c=2627
m=6374, a=2663, c=2627

現在，這是一個 LCG，它只輸出你給出的值而沒有任何間隙。但是我們可以很容易地做一些數學運算來計算出如果 $ a^2 \mod m = 2663 $ ， 然後 $ a = 1200 $ ，2663 的模平方根（在 Mathematica 中，PowerMod[2663, 1/2, 3187]）。

同樣，我們可以很容易地找到 $ c $ . 因此，我們發現 $ m = 3187, a = 1200, c = 854 $ .

因此，實際****序列（奇數項目以粗體****顯示）為****2679、3158、1111、1888、497、1285、346、1744、2982、253、1689、722、390、365、2235、2587、1116、1514 _ _ _ _ _ , 1064, 2854 , …

但也許你擔心我用過 $ \mathrm{O}(n^2) $ 算法？如果什麼 $ m $ 更大？好吧，我只是覺得懶惰，僅此而已。我們可以輕鬆地將復雜性降低到更低的程度。它只是使程式碼稍長一些：

#include <stdio.h>
#include <assert.h>

int modular_inverse(int a, int m)
{
   // Based on code from http://rosettacode.org/wiki/Modular_inverse#C
   int t, nt, r, nr, q, tmp;
   t = 0;  nt = 1;  r = m;  nr = a % m;
   while (nr != 0) {
       q = r/nr;
       tmp = nt;  nt = t - q*nt;  t = tmp;
       tmp = nr;  nr = r - q*nr;  r = tmp;
   }
   if (r > 1) return -1;
   if (t < 0) t += m;
   return t;
}

int main()
{
   enum { X0 = 3158, X1 = 1888, X2 = 1285, X3 = 1744, X4 = 253, X5 = 722,
          M_START = 3159 };

   for (int m = M_START; m < 10*M_START; ++m) {
       int diff0 = (X1 - X0);  if (diff0 < 0) diff0 += m;
       int diff1 = (X2 - X1);  if (diff1 < 0) diff1 += m;
       int diff2 = (X3 - X2);  if (diff2 < 0) diff2 += m;
       int diff3 = (X4 - X3);  if (diff3 < 0) diff3 += m;
       int diff4 = (X5 - X4);  if (diff4 < 0) diff4 += m;

       // diff1 = a * diff0   =>   1/diff0 * diff1 = a
       int inv_diff0 = modular_inverse(diff0, m);
       if (inv_diff0 < 0) continue;
       int a = (diff1 * inv_diff0) % m;

       int my_diff1 = (a * diff0) % m;
       int my_diff2 = (a * diff1) % m;
       int my_diff3 = (a * diff2) % m;
       int my_diff4 = (a * diff3) % m;
       assert(my_diff1 == diff1);

       if (my_diff2 == diff2 && my_diff3 == diff3 && my_diff4 == diff4) {
           printf ("m=%d, a=%d\n", m, a);
       }
   }

   return 0;
}

這個版本基本上是立即吐出答案，執行程序需要 0.001 秒。

m=3187, a=2663

從這裡，我們可以弄清楚 $ c $ 然後如上進行。

順便說一句，如果您喜歡更多挑戰，請隨時查看我不久前提出的這個問題。

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