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 $ ({\rm mod}\ p)$


Author: J. M. Pollard
Journal: Math. Comp. 32 (1978), 918-924
MSC: Primary 10A10; Secondary 65C05
DOI: https://doi.org/10.1090/S0025-5718-1978-0491431-9
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

DOI: https://doi.org/10.1090/S0025-5718-1978-0491431-9
Keywords: Indices, primitive roots, finite fields
Article copyright: © Copyright 1978 American Mathematical Society