Faktorizacija velikih prirodnih brojeva

This paper focuses on prime numbers and factorisation algorithms of large numbers. Prime numbers have only two factors, number 1 and itself, and are one of the fundamental terms in mathematics. Algorithm is a process or set of rules to be followed in calculations or other problem-solving operations. Factorization of large numbers and finding large prime numbers is extremely important in cryptography. In 3rd century BC, Euclid proved that the largest prime number doesn’t exist, and that there are infinite number of primes. As the set of natural numbers continues, they become less frequent, so finding new prime numbers has become a mission for many people. In chapter 1, we will discuss frequency of prime numbers and what are Mersenne’s prime numbers. In chapter 2, we will talk about primality testing. Most basic way to check if a number is prime is by trial division. Fermat’s primality test and Miller-Rabin’s test is also discussed in this paper. If a number \(n\) doesn’t pass one of the primality tests, then we know for sure that \(n\) is a composite number. Even though they are useful for primality testing, these tests rarely give us a non-trivial factor of \(n\). How can we find factors of large numbers, and what is the fastest algorithm to do that? That is considered a hard problem and therefore some of the most important cryptosystems with public key are based on the complexity of factorization. In chapter 3 we will discuss six factorisation algorithms.