×

Monte Carlo methods for index computation (mod \(p\)). (English) Zbl 0382.10001

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.

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
PDFBibTeX XMLCite
Full Text: DOI