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

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]**D. E. KNUTH,*Seminumerical Algorithms, The Art of Computer Programming*, Vol. 2, Addison-Wesley, Reading, Mass., 1969. MR**44**#3531. MR**633878 (83i:68003)****[2]**A. RAPOPORT, "Cycle distributions in random nets,"*Bull. Math. Biophys.*, v. 10, 1948, pp. 145-157. MR**0027494 (10:315a)****[3]**B. HARRIS, "Probability distributions related to random mappings,"*Ann. Math. Statist.*, v. 31, 1960, pp. 1045-1062. MR**0119227 (22:9993)****[4]**J. M. POLLARD, "A Monte Carlo method for factorization,"*BIT*, v. 15, 1975, No. 3, pp. 331-335. MR**52**#13611. MR**0392798 (52:13611)****[5]**R. K. GUY, "How to factor a number,"*Proc. Fifth Manitoba Conf. on Numerical Math.*(Winnipeg, Man., 1975), Univ. of Calgary, Dept. of Math., Statist, and Comp. Sci., Research paper no. 301, Dec. 1975. MR**0404120 (53:7924)****[6]**J. S. DEVITT,*Aliquot Sequences*, M. Sc. Thesis, Dept. of Math. and Stat., Univ. of Calgary, May 1976.**[7]**D. E. KNUTH,*Sorting and Searching, The Art of Computer Programming*, Vol. 3, Addison-Wesley, Reading, Mass., 1973. MR**0445948 (56:4281)****[8]**D. SHANKS, "Class number, a theory of factorization, and genera,"*Proc. Sympos. Pure Math.*, vol. 20, Amer. Math. Soc., Providence, R. I., 1970, pp. 415-440. MR**47**#4932. MR**0316385 (47:4932)****[9]**J. M. POLLARD, "Theorems on factorization and primality testing,"*Proc. Cambridge Philos. Soc.*, v. 76, 1974, pp. 521-528. MR**50**#6992. MR**0354514 (50:6992)****[10]**W. DIFFIE & M. E. HELLMAN, "New directions in cryptography,"*IEEE Trans. Information Theory*, vol. IT-22, No. 6, Nov. 1976, pp. 644-654. MR**0437208 (55:10141)****[11]**J. C. P. MILLER, "On factorization, with a suggested new approach,"*Math. Comp.*, v. 29, 1975, pp. 155-172. MR**0366796 (51:3042)****[12]**MICHAEL A. MORRISON & JOHN BRILLHART, "A method of factoring and the factorization of ,"*Math. Comp.*, v. 29, 1975, pp. 183-205. MR**0371800 (51:8017)****[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 & EMMA LEHMER, "A new factorization technique using quadratic forms,"*Math. Comp.*, v. 28, 1974, pp. 625-635. MR**0342458 (49:7204)**

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