| dc.description.abstract | Algorithm for finding the prime factors of large composite numbers are importance because of the widespread use of public key cryptosystems whose security depends on the presumed difficulty of the factorization problem. This research uses quadratic sieve algorithm for factoring big composite numbers. Quadratic sieve is the best algorithm for factoring composite numbers bellow 100 decimal digits. The quadratic sieve is analyzed and implemented using C programming language and parallelized by functional decomposition and domain decomposition. This research uses additional libraries for parallel implementation and for computing big integer numbers, which are MPI and GMP. The implementation result is tested in a computer with four processors. The factorized composite numbers are 25, 30, and 35 digits. The objectives of this research is to measure and analyze the performance of parallel quadratic sieve algorithm using performance metrics and the complexity of the implemented quadratic sieve. This research uses two ways for parallelizing method: functional decomposition toward sieving stage and domain decomposition on sieving stage. The best result of parallel quadratic sieve is the domain decomposition on sieving stage which has an average efficiency of 91.6%. The result is not good enough because there are an additional task for changing GMP data type to MPI data type on parallel implementation. The complexity of the communication is e^((ln N ln ln N)^(1/2) 10log N + 4 (P-1))/B which means it becomes worse the higher the composite numbers are. Performance metrics also become worse because of the additional task and the communication. | en |
