Modular-Arithmetic
冪模技巧
假設我有
$ p, g $ - 已知常數， $ p $ 是質數， $ g $ 是複合的。
$ x $ - 未知的隨機數， $ 2 < x < p - 1 $
$ k $ - 我的輸入
$ S = k^x \bmod p $
$ 1 < S < p-1 $
所以呢 $ k $ 我應該用來做 $ S $ 可預見？我的意思是，我想知道究竟是什麼 $ S $ 等於。
如果 $ p-1 $ 有一個因子 348419，那麼你可以減少可能值的數量 $ S $ 到 348418 （或 1，你說這是不允許的）。
一種方法是選擇一個隨機值 $ r $ , 併計算 $ k = r^{(p-1)/348419} \bmod p $ ; 如果 $ k $ 不是 1，那麼這就是你的值；最終的 $ S $ 價值將是 $ k^x \bmod p $ 對於一些 $ 1 \le x < 348419 $ .
對於這個特殊的 $ p $ （以及您列出的限制），這是您能做的最好的。