Abstract
Pollard's Monte Carlo factorization algorithm usually finds a factor of a composite integerN inO(N 1/4) arithmetic operations. The algorithm is based on a cycle-finding algorithm of Floyd. We describe a cycle-finding algorithm which is about 36 percent faster than Floyd's (on the average), and apply it to give a Monte Carlo factorization algorithm which is similar to Pollard's but about 24 percent faster.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
M. Beeler, R. W. Gosper and R. Schroeppel,Hakmem, M.I.T. Artificial Intelligence Lab. Memo No. 239, Feb. 1972, item 132, pg. 64.
W. Diffie and M. Hellman,New directions in cryptography, IEEE Trans. Information Theory IT-22 (1976), 644–654.
D. E. Knuth,The Art of Computer Programming, vol. 2, Addison-Wesley, Reading, Mass., 1969.
G. L. Miller,Riemann's hypothesis and a test for primality, Proc. Seventh Annual ACM Symposium on Theory of Computing, ACM, New York, 1975, 234–239.
M. A. Morrison and J. Brillhart,A method of factoring and the factorization of F 7, Math. Comp. 29 (1975), 183–208.
J. M. Pollard,Theorems on factorization and primality testing, Proc. Camb. Phil. Soc. 76 (1974), 521–528.
J. M. Pollard,A Monte Carlo method for factorization, BIT 15 (1975), 331–334. MR50#6992.
J. M. Pollard,Monte Carlo methods for index computation (mod p), Math. Comp. 32 (1978), 918–924. MR52#13611.
M. Rabin,Probabilistic algorithms, inAlgorithms and Complexity (J. F. Traub, ed.), Academic Press, New York, 1976, 31–40.
R. L. Rivest, A. Shamir and L. Adleman,A method for obtaining digital signatures and public-key cryptosystems, Comm. ACM 21 (1978), 120–126.
R. Sedgewick and T. G. Szymanski,The complexity of finding periods, Proc. Eleventh Annual ACM Symposium on Theory of Computing, ACM, New York, 1979, 74–80.
D. Shanks,Class number, a theory of factorization, and genera, Proc. Sympos. Pure Math., vol. 20, Amer. Math. Soc., Providence, Rhode Island, 1970, 415–440. MR47#4932.
R. Solovay and V. Strassen,A fast Monte-Carlo test for primality, SIAM J. Computing 6 (1977), 84–85.
M. C. Wunderlich and J. L. Selfridge,A design for a number theory package with an optimized trial division routine, Comm. ACM 17 (1974), 272–276.
Anonymous,ML-15,Random number generator, TI Programmable 58/59 Master Library, Texas Instruments Inc., 1977, 52–54.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Brent, R.P. An improved Monte Carlo factorization algorithm. BIT 20, 176–184 (1980). https://doi.org/10.1007/BF01933190
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01933190