有什麼加速方法可以找到逆同餘生成器產生的隨機值的索引？
逆同餘生成器產生隨機值： $$ x_{n+1} = a\cdot x_{n}^{-1} + b \mod P $$
（特殊情況如果 $ x_n=0 $ -> $ x_{n+1}=b $ )
從一個初始值開始 $ x_0 $
精心挑選 $ a,b,P $ 它產生所有值 $ \mathbb{F}_P $ （哪個是 $ [0..P-1] $ )
如果沒有 r 就是這種情況 $ r^2 \equiv 4 a + b^2 \mod P $ 和 $ P $ 一個素數。
**問題：**有什麼方法可以計算索引 $ n $ 對於給定的值 $ v \in \mathbb{F}_P $ 和 $ x_n=v $ ? （和 $ a,b,P $ 精心選擇和眾所周知）
或者有什麼方法可以比蠻力更快地計算它？
為了 $ n $ ’th 隨機值方程存在： $$ x_n=(q_{n+1}\cdot x_0 + a\cdot q_n)(q_{n}\cdot x_0 + a\cdot q_{n-1})^{-1} \mod P $$ 和 $ q $ 又是一個序列： $$ q_0=0 $$ $$ q_1=1 $$ $$ q_{n}=a\cdot q_{n-2}+b\cdot q_{n-1} (\mod P) $$
q 類似於斐波那契數列。沒有模有一個方程 $ n $ ’th 元素： $$ q_n= \frac{ (\frac{b +\sqrt{4 a + b^2} }{2})^n - (\frac{b - \sqrt{4 a + b^2}}{2})^n}{\sqrt{4 a + b^2}} $$ （不知道是否也存在取模形式 $ P $ )
更新： $ q_n $ 以P 為模的方程
：
$ r^2 \equiv 4 \cdot a+b^2 \mod P $
$ 1 \equiv t \cdot 2 \mod P $
$$ q_n = ((b+r)^n-(b-r)^n)\cdot t^n \cdot r^{-1} \mod P $$ 這個等式也適用於 $ \mathbb{F}_P $
但是對於目標值 $ a,b $ 不存在這樣的根 $ r $ .
（對於他人 $ a,b $ 它不能產生它確實起作用的所有值）
更新 2：簡化
為了簡化，我們可以假設 $ x_0=0 $ . 有了這個方程 $ x_n $ 將會： $$ x_n=(a\cdot q_n)(a\cdot q_{n-1})^{-1} \mod P $$ $$ x_n=q_n\cdot q_{n-1}^{-1} \mod P $$
任何計算索引的方法 $ n $ 對於給定值 $ v=x_n $ ?
更新 3：wolframalpa
wolfram alpha 中的一些測試有一個非模數版本的解決方案（與 $ x0=0 $ ): https://www.wolframalpha.com/input/?i=solve+(((b%2Br)%2F2)^n-((b-r)%2F2)^n)%2F(((b%2Br)%2F2)^(n-1)-((b-r)%2F2)^(n-1))%3Dv+for+n?
$$ n = \frac{ \log(\frac{(b - r) (b + r - 2 v)} {(b + r) (b - r - 2 v)}) + 2 i \pi c_1}{\log(b - r) - \log(b + r)} $$
使用這個我得到一個複數 $ n $ 有實部和虛部 $ \not\in \mathbb{N} $ . 如果我計算 $ x_n=q_n/q_{n-1} $ 有了這個 $ v $ 在 $ \mathbb{R} $ 例如，它確實有效。
知道如何將其轉換為 $ \mod P $ （對於值 $ a,b $ 沒有根 $ r $ )?
或者如何轉換 $ v\in \mathbb{F}_P $ 至 $ \mathbb{R} $ ?
更新4：擺脫 $ r $ 在 $ q_n $ 方程
$ q_n $ 可以在頂部和底部相乘 $ r $ 要得到 $ r^2 $ 只要。和 $ x0=0 $ 方程為 $ x_n $ 將是（對於 $ n>2 $ ): $$ x_n=q_n q_{n-1}^{-1}= \frac{2 \cdot \sum_{k=1}^{\lfloor n/2\rfloor} {n-1\choose 2k-1} b^{n-2k}(r^2)^{k} }{4\cdot \sum_{k=1}^{\lfloor (n-1)/2 \rfloor} {n-2 \choose 2k- 1} b^{n-2k-1} (r^2)^{k } } \mod P $$
下半部分必須是倒數，而不是除數 $ \mod P $ .
但是我看不到任何方法可以提取公式 $ n $ 出此。我錯過了什麼嗎？
（評論太長了）
你可以計算 $ x_n $ 直接通過你的公式，如果你知道，如何在素數域的二次擴展域中計算 $ \mathbb{F}_p $ .
這是python中的程式碼：
# global parameters p = 65537 t = (p+1)/2 r = 313 s = 997 # from https://stackoverflow.com/a/9758173/99978 # modular inverse based on extended Euclidean algorithm def egcd(a, b): if a == 0: return (b, 0, 1) else: g, y, x = egcd(b % a, a) return (g, x - (b // a) * y, y) def modinv(a, m): g, x, y = egcd(a, m) if g != 1: raise Exception('modular inverse does not exist') else: return x % m # for generating sequence x_n def succ(x): return (r*modinv(x, p)+s) % p # check that 4*r+s^2 does not have any root mod p for i in range(t): if (i*i) % p == (4*r+s*s) % p: raise Exception('not irreducible') # conjugate in field def conj(x): a, b = x return [a, -b] # subtraction in field def minus(x, y): a, b = x c, d = y return [(a-c)%p, (b-d)%p] # multiplication of a+bX with c+dX in field F_p/[X^2+4*r+s^2] def mult(x, y): a, b = x c, d = y return [(a*c+b*d*(4*r+s*s)) % p, (a*d+b*c) % p] # exponentiation in field def exp(x, n): y = [1, 0] while n > 0: if n % 2 == 1: y = mult(y, x) x = mult(x, x) n = n/2 return y # inverse in field (same as exp(x, p*p-2)) def inv(x): a, b = mult(x, conj(x)) if b != 0: raise Exception('error in inverse') return mult([modinv(a, p), 0], conj(x)) # your formula for q_n def qn(n): x, y = mult(mult(minus(exp([s, 1], n), exp([s, -1], n)), exp([t, 0], n)), inv([0, 1])) return x # your formula for x_n given q_n def xn(x0, n): return ((qn(n+1)*x0+r*qn(n))*modinv(qn(n)*x0+r*qn(n-1), p)) % p # a short test x = 97 for i in range(500): x = succ(x) if xn(97, i+1) != x: raise Exception('wrong result')擴展素數域 $ \mathbb{F}_p $ （“素數域”是最小域，有限域是有序域 $ p $ ，無窮大是 $ \mathbb{Q} $ ) 由元素的平方根 $ z\in\mathbb{F}_p $ 沒有根的 $ \bmod p $ 工作方式與擴展實數相同 $ \mathbb{R} $ 對複數 $ \mathbb{C} $ : 發明一個元素 $ X $ 誰的正方形是 $ z $ （為了 $ \mathbb{C} $ 這通常被稱為 $ i $ )，並用形狀數計算 $ a+bX $ 使用 $ X^2 = z $ .
正式糾正這可以通過多項式環中的計算來完成 $ \mathbb{F_p}[X] $ 模多項式 $ X^2-z $ 或者在上面看到的程式碼中。
您可以通過使用共軛（替換 $ X $ 經過 $ -X $ ) 是在現場使用加法/乘法/求冪進行通勤，但我懷疑你是否能夠反轉函式 $ n\mapsto x_n $ .