Pembangkitan Bilangan Prima dengan Metode Saringan Eratosthenes

Abstract

Cryptograph is required in securing information or data transmission. In cryptograph, prime numbers are required in high level message security. These prime numbers are acquired by generation method. There are many considerable methods which can be implemented to find prime numbers, one of them is the sieve of Eratosthenes method. There is another method to generate prime numbers, which is called Miller-Rabin prime test algorithm. The aims of this paper are to study and implement the sieve of Eratosthenes method and Miller-Rabin prime test algorithm, and then to compare these algorithms. The sieve of Eratosthenes method is applied to find all prime numbers up to a specified integer n. The filtering is acquired by determining all prime numbers which are smaller or equal to L J;, J and cancelling all integers which are multiple of these prime numbers. In Miller-Rabin prime test algorithm all prime numbers in one interval is determined by applying a certain test to each number within this interval. According to the implementation results, time requirement to execute the sieve Eratosthenes algorithm is shorter than the Miller-Rabin prime test algorithm. The sieve Eratosthenes algorithm needs o( n(lgn)2Ig Ign) bit operations, while generation of prime numbers using Miller-Rabin prime test algorithm needs O({10gnf) bit operations. Nevertheless, the memory requirement of sieve Eratosthenes is higher than Miller-Rabin prime test algorithm. It is because the sieve Eratosthenes algorithm consumes n array and memory consumption of the Miller-Rabin prime test algorithm is negligible (constant).