UPM Institutional Repository

Modified Miller-Rabin primality test algorithm to detect prime numbers for generating RSA keys


Shereek, Balkees Mohamed (2016) Modified Miller-Rabin primality test algorithm to detect prime numbers for generating RSA keys. Masters thesis, Universiti Putra Malaysia.


A prime number is a number that is only divisible by one and itself, which is essentially saying that it has no divisor. Prime numbers are important in the security field because many encryption algorithms are based on the fact that it is very easy to multiply two large prime numbers and get the result, while it is extremely computerintensive to do the reverse. The Rivest-Shamir-Adleman algorithm (RSA) is one of the most well-known and strongest public key cryptography algorithms. The security of the RSA depends on the two prime numbers namely p and q and to generate them is an extremely time consuming process (Fu and Zhu, 2008). An efficient method for generating large random prime numbers within shortest time is thus a crucial challenge for researchers (Bahadori et al., 2010; Saveetha and Arumugam, 2012). The objective of this study is to reduce the time taken in finding prime numbers p and q for RSA. To achieve the objective, the Miller-Rabin primality test was modified by adding few tests in the original Miller-Rabin. The prime numbers with the size of 256, 512, and 1024 bits are generated using the proposed modified algorithm. The performance of the proposed modified Miller-Rabin was analysed in terms of the time taken to detect the prime numbers and compare the time taken for generating the prime numbers using original Miller-Rabin method. The comparison between the original Miller- Rabin and the modified Miller-Rabin primality test methods show the difference of time to generate prime numbers and the modified method shown the better results. The study also reviewed previous works and the modified Miller-Rabin primality test method has shown the better results in compared to them.

Download File

FSKTM 2016 21 IR.pdf

Download (1MB) | Preview

Additional Metadata

Item Type: Thesis (Masters)
Subject: Data encryption (Computer science) - Mathematical models
Subject: Numbers, Prime
Subject: Algorithms
Call Number: FSKTM 2016 21
Chairman Supervisor: Madam Hajah Zaiton Muda
Divisions: Faculty of Computer Science and Information Technology
Depositing User: Ms. Nur Faseha Mohd Kadim
Date Deposited: 10 Jul 2019 03:40
Last Modified: 10 Jul 2019 03:40
URI: http://psasir.upm.edu.my/id/eprint/69356
Statistic Details: View Download Statistic

Actions (login required)

View Item View Item