Monte Carlo methods for index computation (𝑚𝑜𝑑𝑝)

Pollard, J. M.

doi:10.1090/S0025-5718-1978-0491431-9

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

Aliquot Sequences

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

Math. Comp.

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