×

An improved Monte Carlo factorization algorithm. (English) Zbl 0439.65001


MSC:

11Y05 Factorization
65C05 Monte Carlo methods
11-04 Software, source code, etc. for problems pertaining to number theory
65C10 Random number generation in numerical analysis
65-04 Software, source code, etc. for problems pertaining to numerical analysis
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] M. Beeler, R. W. Gosper and R. Schroeppel,Hakmem, M.I.T. Artificial Intelligence Lab. Memo No. 239, Feb. 1972, item 132, pg. 64.
[2] W. Diffie and M. Hellman,New directions in cryptography, IEEE Trans. Information Theory IT-22 (1976), 644–654. · Zbl 0435.94018 · doi:10.1109/TIT.1976.1055638
[3] D. E. Knuth,The Art of Computer Programming, vol. 2, Addison-Wesley, Reading, Mass., 1969. · Zbl 0191.18001
[4] 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.
[5] M. A. Morrison and J. Brillhart,A method of factoring and the factorization of F 7, Math. Comp. 29 (1975), 183–208. · Zbl 0302.10010
[6] J. M. Pollard,Theorems on factorization and primality testing, Proc. Camb. Phil. Soc. 76 (1974), 521–528. · Zbl 0294.10005 · doi:10.1017/S0305004100049252
[7] J. M. Pollard,A Monte Carlo method for factorization, BIT 15 (1975), 331–334. MR50#6992. · Zbl 0312.10006 · doi:10.1007/BF01933667
[8] J. M. Pollard,Monte Carlo methods for index computation (mod p), Math. Comp. 32 (1978), 918–924. MR52#13611. · Zbl 0382.10001
[9] M. Rabin,Probabilistic algorithms, inAlgorithms and Complexity (J. F. Traub, ed.), Academic Press, New York, 1976, 31–40.
[10] R. L. Rivest, A. Shamir and L. Adleman,A method for obtaining digital signatures and public-key cryptosystems, Comm. ACM 21 (1978), 120–126. · Zbl 0368.94005 · doi:10.1145/359340.359342
[11] 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.
[12] 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.
[13] R. Solovay and V. Strassen,A fast Monte-Carlo test for primality, SIAM J. Computing 6 (1977), 84–85. · Zbl 0345.10002 · doi:10.1137/0206006
[14] 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. · Zbl 0276.68025 · doi:10.1145/360980.361001
[15] Anonymous,ML-15,Random number generator, TI Programmable 58/59 Master Library, Texas Instruments Inc., 1977, 52–54.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.