Cycle detection, order finding and discrete log with jumps
Sourav Chakraborty, David García-Soriano, Arie Matsliah · 2011
Determining s and r, given a ∈ S and a black-box oracle to f, is the cycle-detection problem. When f is bijective (i.e., f is a permutation of S), the order-finding problem is to find the smallest r> 0 such that f r (a) = a, and the discrete-log problem is, given an additional element b ∈ S, to find the smallest k ≥ 0 such that f k (a) = b. We study the query complexity of these problems with oracles that allow “jumps ” to distant positions in the sequence ā � f 0 (a)f 1 (a)f 2 (a) · · · ∈ S ∗ at unit cost. Specifically, for every m ∈ N the oracle Om f is defined, which for every a ∈ S allows to look ahead at any position i < m in the sequence ā; that is, O m f (a, i) = f i (a) for every (a, i) ∈ S × [m]. We show that with an unrestricted oracle O ∞ f, the cycle-detection and order-finding problems can be solved using O(log s+log r / log log log r) and O(log r / log log log r) queries, respectively, regardless of |S|. This is nearly optimal, as we also prove lower bounds of Ω(log s + log r / log log r) and Ω(log r / log log r) queries. Interestingly, for the discrete-log problem, our results combined with the algorithm of Sutherland [8] imply a lower bound of Ω ( √ r / log r) queries (where r is the size of the cycle to which both a and b belong), which is tight up to the log r factor. This contrasts with the fact that, with generic group-operation oracles, the problems of order finding and discrete log are known to have polynomially related query complexities. We also provide algorithms and lower bounds for general oracles Om f, m ∈ N, improving results from earlier work. In particular, with m = poly(r), our lower bound for order-finding improves the previous bound of ˜ Ω(r1/3) queries, proved by Cleve [2], to ˜ Ω(r1/2), which is nearly optimal.