Parallel Implementation of Elliptic Curve Method for Integer Factorization Using Message-Passing Interface (MPI)
Resumo
One of the most prominent systems for securing eletronic information, known as RSA (Rivest-Shamir-Adleman) [RIV78], relies upon the fact that it is computationally difficult to factor a large integer into its component prime integers. lf an efficient algorithm is developed that can factor any arbitrarily large integer in a reasonable amount of time, the security value of the RSA system would be nullified. In this paper we present the Elliptic Curve Method for integer factorization and results of its parallel implementation using Message-Passing Interface (MPI).
Palavras-chave:
Integer factorization, RSA, Elliplic Curve Method, Parallel Processing, Cluster Computing
Referências
LENSTRA, A. K. and LENSTRA, H. W. Jr. (editors). The Development of the Number Field Sieve. Lecture Notes on Mathematics 1554, Springer-Verlag, Bcrlin, 1993.
FOSTER, I. Designing and Building Parallel Programs. Addison-Wesley Longman,lnc., Sidney, Australia, 1995.
SILVERMAN, J. H. The Arithmetic of Elliptic Curves. volume 106 of Graduate Texts in Mathematics, page 131, SpringerVerlag, New York, 1986.
RIVEST. R. L.; SHAMIR, A.; ADLEMAN, L. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, v.21. p. l20-126. 1978.
LENSTRA, H. W. Jr. Factoring integers with elliptic curves. Annals of Mathematics, v. 126, p.649-673, 1987.
POMERANCE, C. The quadratic sieve factoring algorithm. Advances in Cryptology, Proc. Eurocrypt '84, v.LNCS 209, I p. 169-182, 1985.
LENSTRA, A. K.; LENSTRA. H. W. Jr.; MANASSE, M. S.; POLLARD, J. M. The number field sieve. Proc 22nd Annual ACM Conference on Theory of Computing. Baltimore, Maryland, p.564-572, 1990.
MPI-Forum. MPI: A Message-Passing Interface Standard. International Journal of Supercomputer Application, v.8, n.3-4, 1994.
PARALLEL COMPUTING, Special issue: Message passing interface. Parallel Computing. v.20. n.4, 1994.
BRENT, R. P. Factorization of the tenth Fermat number. Math. Comp., v.68, p.429-451, 1999.
BRENT. R. P. Some integer factorisation algorithms using elliptic curves. Australian Computer Science Communications, v.8, p. 149-163, 1986.
DIXON, B.; LENSTRA, A. K. Massively parallel elliptic curve factoring. Proc. Eurocrypt'92, v.LNCS 658, p.183-193. 1993.
BRENT, R. P. Some parallel algorithms for integer factorization. European Conference on Parallel Processing, p. 1-22, 1999.
LENSTRA, A. K.; VERHEUL, E. R. Selecting Cryptographic Key Sizes. http://www.cryptosavvy.com/, 1999.
ZIMMERMAN, P. The ECMNET Project. http://www.loria.fr/~zimmerma/records/ecmnet.html, 1999.
BRENT, R. P. Large factors found by ECM. Oxford University Computing Laboratory [link] 2000.
DANTAS, M. A. R.; LOPES, F. M. lmproving load balancing in a parallel cluster environment using mobile agents. Accepted paper HPCN2001 Europe, Amsterdam, 2001.
SHAMUS SOFTWARE. Miracl. http://indigo.ie/~mscott/, 2001.
ADVANCED COMPUTING LABORATORY. POOMA. http://www.acl.lanl.gov/pooma, 2001.
FOSTER, I. Designing and Building Parallel Programs. Addison-Wesley Longman,lnc., Sidney, Australia, 1995.
SILVERMAN, J. H. The Arithmetic of Elliptic Curves. volume 106 of Graduate Texts in Mathematics, page 131, SpringerVerlag, New York, 1986.
RIVEST. R. L.; SHAMIR, A.; ADLEMAN, L. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, v.21. p. l20-126. 1978.
LENSTRA, H. W. Jr. Factoring integers with elliptic curves. Annals of Mathematics, v. 126, p.649-673, 1987.
POMERANCE, C. The quadratic sieve factoring algorithm. Advances in Cryptology, Proc. Eurocrypt '84, v.LNCS 209, I p. 169-182, 1985.
LENSTRA, A. K.; LENSTRA. H. W. Jr.; MANASSE, M. S.; POLLARD, J. M. The number field sieve. Proc 22nd Annual ACM Conference on Theory of Computing. Baltimore, Maryland, p.564-572, 1990.
MPI-Forum. MPI: A Message-Passing Interface Standard. International Journal of Supercomputer Application, v.8, n.3-4, 1994.
PARALLEL COMPUTING, Special issue: Message passing interface. Parallel Computing. v.20. n.4, 1994.
BRENT, R. P. Factorization of the tenth Fermat number. Math. Comp., v.68, p.429-451, 1999.
BRENT. R. P. Some integer factorisation algorithms using elliptic curves. Australian Computer Science Communications, v.8, p. 149-163, 1986.
DIXON, B.; LENSTRA, A. K. Massively parallel elliptic curve factoring. Proc. Eurocrypt'92, v.LNCS 658, p.183-193. 1993.
BRENT, R. P. Some parallel algorithms for integer factorization. European Conference on Parallel Processing, p. 1-22, 1999.
LENSTRA, A. K.; VERHEUL, E. R. Selecting Cryptographic Key Sizes. http://www.cryptosavvy.com/, 1999.
ZIMMERMAN, P. The ECMNET Project. http://www.loria.fr/~zimmerma/records/ecmnet.html, 1999.
BRENT, R. P. Large factors found by ECM. Oxford University Computing Laboratory [link] 2000.
DANTAS, M. A. R.; LOPES, F. M. lmproving load balancing in a parallel cluster environment using mobile agents. Accepted paper HPCN2001 Europe, Amsterdam, 2001.
SHAMUS SOFTWARE. Miracl. http://indigo.ie/~mscott/, 2001.
ADVANCED COMPUTING LABORATORY. POOMA. http://www.acl.lanl.gov/pooma, 2001.
Publicado
10/09/2001
Como Citar
WOLSKI, E.; S. FILHO, Joel G.; DANTAS, M. A. R..
Parallel Implementation of Elliptic Curve Method for Integer Factorization Using Message-Passing Interface (MPI). In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 13. , 2001, Pirenópolis.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2001
.
p. 44-49.
DOI: https://doi.org/10.5753/sbac-pad.2001.22191.
