Designing Fast Algorithms Using Parallel Models

Abstract

RSA is one of the most important public key cryptosystems for information security. The security of RSA depends on integer factorization problem, it relies on the di culty of factoring large integers. The General Number Field Sieve algorithm (GNFS) is currently the best known method for factoring large numbers over than 100 digits. The algorithm consists of ve main steps. The third step, which is sieving step, takes the most time consumed in GNFS algorithm as proved in previous researches.In this thesis, we improve the running time of this step by parallels it on a cluster system. We proposed the di erent techniques to improve the running time of this step. The experimental results have shown that the algorithm has achieved a good speedup and can be used for factoring a large integers.