Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Monte Carlo methods for index computation $(\textrm {mod}\ p)$

Author: J. M. Pollard
Journal: Math. Comp. 32 (1978), 918-924
MSC: Primary 10A10; Secondary 65C05
MathSciNet review: 0491431
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: 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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 10A10, 65C05

Retrieve articles in all journals with MSC: 10A10, 65C05

Additional Information

Keywords: Indices, primitive roots, finite fields
Article copyright: © Copyright 1978 American Mathematical Society