No label defined (Q4249708)

The paper under review analyzes \textit{D. Shanks's} algorithm [Proc. 2nd Manit. Conf. Numer. Math., Winnipeg 1972, 51-70 (1973; Zbl 0307.10015)] for computing square roots in the finite field \(F_p\), for any prime \(p \neq 2\). The complexity analysis is in terms of the order \(n\) of \(p\), defined by expressing \(p - 1 = 2^n q\) with \(q\) odd. It is shown that Shanks's algorithm (after initialization) uses an average of \({1 \over 4} (n^2 + 7n - 12) + {1 \over 2^{n - 1}}\) multiplications in \(F_p\) for a fixed prime \(p\) of order \(n\), and uses \(8/3\) multiplications averaged over all primes. The argument is a nice blend of standard combinatorical techniques (such as solving linear recurrence relations with constant coefficients), number theory (such as Dirichlet's theorem on arithmetic progressions), and real analysis (such as Lebesgue's Dominated Convergence Theorem to exchange limiting processes). The initialization step is also analyzed and shown to require (under relatively mild assumptions) \(3\lfloor \log q \rfloor + 1\) multiplications on average. Thus Shanks's algorithm is shown to be very fast despite its \(O(n^2)\) worst case time complexity because most of the time \(n\) is very small. The second moment of the distribution of the number of multiplications is also computed and shown to be asymptotic to \({1 \over 16} n^4\) for a fixed prime of order \(n\) and \(36{2 \over 9}\) averaged over all primes (again excluding the initialization). As the order \(n\) goes to infinity, the limiting distribution of the number of multiplications is (essentially) normal with mean asymptotic to \({1 \over 4}n^2\) and variance \(\theta (n^{3/2})\). The author points out that in practice it is probably better to use a different algorithm for those primes with large orders. For example, it is noted that Peralta's algorithm [\textit{R. C. Peralta}, IEEE Trans. Inform. Theory 32, 846-847 (1986; Zbl 0658.68043)] runs slightly faster when the order is large, but is about three times slower than Shanks's algorithm when the order is small. For the entire collection see [Zbl 0910.00037].