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

HTML articles powered by AMS MathViewer

- by J. M. Pollard PDF
- Math. Comp.
**32**(1978), 918-924 Request permission

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

- Donald E. Knuth,
*The art of computer programming. Vol. 2*, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR**633878** - Anatol Rapoport,
*Steady states in random nets. II*, Bull. Math. Biophys.**10**(1948), 221โ226. MR**27494**, DOI 10.1007/bf02477504 - Bernard Harris,
*Probability distributions related to random mappings*, Ann. Math. Statist.**31**(1960), 1045โ1062. MR**119227**, DOI 10.1214/aoms/1177705677 - J. M. Pollard,
*A Monte Carlo method for factorization*, Nordisk Tidskr. Informationsbehandling (BIT)**15**(1975), no.ย 3, 331โ334. MR**392798**, DOI 10.1007/bf01933667 - Richard K. Guy,
*How to factor a number*, Proceedings of the Fifth Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1975) Congressus Numerantium, No. XVI, Utilitas Math. Publ., Winnipeg, Man., 1976, pp.ย 49โ89. MR**0404120**
J. S. DEVITT, - Donald E. Knuth,
*The art of computer programming. Volume 3*, Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1973. Sorting and searching. MR**0445948** - 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** - J. M. Pollard,
*Theorems on factorization and primality testing*, Proc. Cambridge Philos. Soc.**76**(1974), 521โ528. MR**354514**, DOI 10.1017/s0305004100049252 - Whitfield Diffie and Martin E. Hellman,
*New directions in cryptography*, IEEE Trans. Inform. Theory**IT-22**(1976), no.ย 6, 644โ654. MR**437208**, DOI 10.1109/tit.1976.1055638 - J. C. P. Miller,
*On factorisation, with a suggested new approach*, Math. Comp.**29**(1975), 155โ172. MR**366796**, DOI 10.1090/S0025-5718-1975-0366796-6 - Michael A. Morrison and John Brillhart,
*A method of factoring and the factorization of $F_{7}$*, Math. Comp.**29**(1975), 183โ205. MR**371800**, DOI 10.1090/S0025-5718-1975-0371800-5
D. H. LEHMER, "An announcement concerning the Delay Line Sieve DLS 127," - D. H. Lehmer and Emma Lehmer,
*A new factorization technique using quadratic forms*, Math. Comp.**28**(1974), 625โ635. MR**342458**, DOI 10.1090/S0025-5718-1974-0342458-5

*Aliquot Sequences*, M. Sc. Thesis, Dept. of Math. and Stat., Univ. of Calgary, May 1976.

*Math. Comp.*, v. 20, 1966, pp. 645-646.

## Additional Information

- © Copyright 1978 American Mathematical Society
- 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