ICS 2011

Welcome to ICS2011

Innovations in Computer Science - ICS 2011, Tsinghua University, Beijing, China, January 7-9, 2011. Proceedings, 284-297, 978-7-302-24517-9
Tsinghua University Press

Cycle Detection, Order Finding and Discrete Log with Jumps Authors : Sourav Chakraborty, David Garcίa-Soriano, Arie Matsliah [Download PDF]

Abstract:
Let S be a finite set. Given a function f : S → S and an element a ∈ S, define f0(a) = a and fi(a) = f(fi−1(a)) for all i ≥ 1. Let s ≥ 0 and r > 0 be the smallest integers such that fs(a) = fs+r(a). 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 fr(a) = a, and the discrete-log problem is, given an additional element b ∈ S, to find the smallest k ≥ 0 such that fk(a) = b. We study the query complexity of these problems with oracles that allow "jumps" to distant positions in the sequence ā f0(a)f1(a)f2(a)... ∈ S* at unit cost. Specifically, for every m ∈ N the oracle Omf is defined, which for every a ∈ S allows to look ahead at any position i < m in the sequence ā; that is, Omf (a, i) = fi(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 Ω( / 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 Omf , 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.

Preview: