An efficient Parallel Implementation of Self Initialization Quadratic Sieve for Integer Factorizations Using Message Passing Interface (MPI)

Integer factorization is one of the most important topics in the complex computation domain. With the advent of public key cryptosystems it is also of practical importance. One method used to factor large composite numbers is the Multiple Polynomial Quadratic Sieve. This paper proposes an optimized serial implementation of one of the best variants of the Multiple Polynomial Quadratic Sieve and then presents an efficient parallel version of this serial implementation using the Message Passing Interface (MPI). We also discuss the performance of this implementation.

کلیدواژه ها:

Integer factorization ، RSA Cryptosystem ، Self Initializating Quadratic Sieve algorithm ، Cluster ، Message Passing Interface