Analysis on Sieve of Eratosthenes algorithm and algorithms for solving the discrete logarithm problem

• Main Author: Loo, Jia Ein
• Other Authors: Tay Kian Boon
• Format: Final Year Project
• Language: English
• Published: Nanyang Technological University 2023
• Subjects: Engineering::Computer science and engineering
• Online Access: https://hdl.handle.net/10356/166054
• Institution: Nanyang Technological University

This paper explores 3 problems, the Sieve of Eratosthenes, Discrete Logarithm Problem (DLP) and Integer Factorization. Prime numbers are essential to all cryptographic systems today. The Sieve of Eratosthenes is an algorithm used to find prime numbers up to a given limit. Using the basic version of the algorithm will work but take a long time just to produce prime numbers below the limit of one billion. Here we explore some improvements on the algorithm and implemented them. The DLP is defined as: given a group Fp, a generator g of the group and an element k of p, find the discrete logarithm to the base g of k in the group p. k = gα mod p From the equation above, we want to find a, given k, g and p. The DLP is known to be a computationally hard problem and is hence is used to construct a secure cryptosystem. However, the DLP is not always hard – it depends on the groups. In this paper, we explore algorithms to exploit weak groups and solve their discrete logarithm efficiently. Integer Factorization is necessary for many other algorithms, such as the Pohlig-Hellman algorithm (which will be explained later in this paper), where factors of a number are required for the algorithm. Integer Factorization is a known NP problem, and there is no algorithm yet that can solve it in polynomial time. The goal of integer factorization is to decompose a number into smaller numbers, also known as prime factors. In this paper, we evaluate different integer factorization algorithms, understanding the constraints of each algorithm.