可以在少於 N 次的操作中計算具有 N 次迭代的“(input * X) mod Y”嗎？

我想了一個簡單的問題，但問題就在這裡（很抱歉我缺乏數學符號技能）：

給定輸入 I、固定因子 X 和固定模 Y 和 N 次迭代，該過程是否需要在 N 步中連續執行，還是可以加快速度？

I=12345
X=655573
Y=54321
for N=0; N < 10000; N++ {
   I=(I*Y)%X
}

沒有任何秘密（當然除了輸出），想法是有一個函式只使用乘法（可能還有加法）和 mod（沒有比較/如果）在執行大量迭代時產生不可預測的結果，就像散列雜湊 N 次

如果您對存在“一個秘密”感到滿意（儘管您根本不需要儲存它），那麼這種形式有一個簡單的構造（幾乎就是您已經擁有的那個）。

讓 $ N = pq $ 是一個 RSA 偽素數。定義函式： $$ f^0(m) = m\bmod N,\quad f^{i+1}(m) = (f^i(m))^2\bmod N $$

然後假設該函式本質上是連續的（因此具有您想要的“不可預測的結果”），前提是分解 N 很困難。請注意，這只是一個猜想— 分解 N 可能很困難，而且這個函式可能是可並行的（但這個問題已經存在了幾十年）。

我將把你的函式寫成： $$ g^0(m) = m\bmod N,\quad g^{i+1}(m) = Yg^i(m)\bmod N $$

功能 $ f $ 與您的功能不同 $ g $ 在兩個重要方面。

1. 它在每一步“平方”（因此 $ f^i(m) = m^{2^i}\bmod N $ )，而不是乘以 $ Y $ （產生 $ g^i(m) = mY^i\bmod N $ ).
2. 這個需要 $ N = pq $ 足夠大以至於 RSA 很難（比如最少 2048 位，雖然可能是 4096）。

這兩項似乎都需要改變：

1. 第一個允許預處理攻擊（計算表 $ g^{2^i}(1) $ 為了 $ i\in [\log N] $ ，那麼你可以計算 $ g^j(m) = m\prod_{i\in[\log N]}g^{b_i2^i}(1) $ ， 在哪裡 $ b_i $ 是二元分解 $ j $ ）。這顯然可以並行化。
2. 如果 $ N $ 太小了，你可以考慮一下 $ p, q $ ，然後計算 $ g^i(m) = mY^i\bmod N = mY^{i\bmod (p-1)(q-1)}\bmod N $ ，然後您可以有效地計算。

這裡提到的“一個秘密”就是因式分解 $ N = pq $ .

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