Pollard, J. M. Monte Carlo methods for index computation (mod \(p\)). (English) Zbl 0382.10001 Math. Comput. 32, 918-924 (1978). Summary: We describe some novel methods to compute the index of any integer relative to a given primitive root of a prime \(p\). Our first method avoids the use of stored tables and apparently requires \(O(p^{1/2})\) operations. Our second algorithm, which may be regarded as a method of catching kangaroos, is applicable when the index is known to lie in a certain interval; it requires \(O(w^{1/2})\) operations for an interval of width \(w\), but does not have complete certainty of success. It has several possible areas of application, including the factorization of integers. Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page Cited in 5 ReviewsCited in 125 Documents MSC: 11-04 Software, source code, etc. for problems pertaining to number theory 11A07 Congruences; primitive roots; residue systems 11Y16 Number-theoretic algorithms; complexity 11A41 Primes Keywords:computation of the index of an integer relative to a given primitive root of a prime PDFBibTeX XMLCite \textit{J. M. Pollard}, Math. Comput. 32, 918--924 (1978; Zbl 0382.10001) Full Text: DOI