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, Aliquot Sequences, M. Sc. Thesis, Dept. of Math. and Stat., Univ. of Calgary, May 1976.
- 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," Math. Comp., v. 20, 1966, pp. 645-646.
- 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
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