Monte Carlo methods for index computation

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

**[1]**Donald E. Knuth,*The art of computer programming. Vol. 2*, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR**633878****[2]**Anatol Rapoport,*Steady states in random nets. II*, Bull. Math. Biophys.**10**(1948), 221–226. MR**0027494****[3]**Bernard Harris,*Probability distributions related to random mappings*, Ann. Math. Statist.**31**(1960), 1045–1062. MR**0119227**, https://doi.org/10.1214/aoms/1177705677**[4]**J. M. Pollard,*A Monte Carlo method for factorization*, Nordisk Tidskr. Informationsbehandling (BIT)**15**(1975), no. 3, 331–334. MR**0392798****[5]**Richard K. Guy,*How to factor a number*, Proceedings of the Fifth Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1975) Utilitas Math. Publ., Winnipeg, Man., 1976, pp. 49–89. Congressus Numerantium, No. XVI. MR**0404120****[6]**J. S. DEVITT,*Aliquot Sequences*, M. Sc. Thesis, Dept. of Math. and Stat., Univ. of Calgary, May 1976.**[7]**Donald E. Knuth,*The art of computer programming. Volume 3*, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1973. Sorting and searching; Addison-Wesley Series in Computer Science and Information Processing. MR**0445948****[8]**Daniel Shanks,*Class number, a theory of factorization, and genera*, 1969 Number Theory Institute (Proc. Sympos. Pure Math., Vol. XX, State Univ. New York, Stony Brook, N.Y., 1969) Amer. Math. Soc., Providence, R.I., 1971, pp. 415–440. MR**0316385****[9]**J. M. Pollard,*Theorems on factorization and primality testing*, Proc. Cambridge Philos. Soc.**76**(1974), 521–528. MR**0354514****[10]**Whitfield Diffie and Martin E. Hellman,*New directions in cryptography*, IEEE Trans. Information Theory**IT-22**(1976), no. 6, 644–654. MR**0437208****[11]**J. C. P. Miller,*On factorisation, with a suggested new approach*, Math. Comp.**29**(1975), 155–172. Collection of articles dedicated to Derrick Henry Lehmer on the occasion of his seventieth birthday. MR**0366796**, https://doi.org/10.1090/S0025-5718-1975-0366796-6**[12]**Michael A. Morrison and John Brillhart,*A method of factoring and the factorization of 𝐹₇*, Math. Comp.**29**(1975), 183–205. Collection of articles dedicated to Derrick Henry Lehmer on the occasion of his seventieth birthday. MR**0371800**, https://doi.org/10.1090/S0025-5718-1975-0371800-5**[13]**D. H. LEHMER, "An announcement concerning the Delay Line Sieve DLS 127,"*Math. Comp.*, v. 20, 1966, pp. 645-646.**[14]**D. H. Lehmer and Emma Lehmer,*A new factorization technique using quadratic forms*, Math. Comp.**28**(1974), 625–635. MR**0342458**, https://doi.org/10.1090/S0025-5718-1974-0342458-5

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