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

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?)

  • [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 $ {F_7}$," 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)

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

American Mathematical Society