Hello everyone! I am back with another entry in my Magic of Computing series. Today, we are going to have one last look at prime numbers. During the previous article, we learned about an influential figure in the world of science, Eratosthenes of Cyrene, and today we are going to see how a prime factorisation algorithm performs, use some of Erastothenes' findings to improve it, and explain why we care about prime factorisation in the first place.
What is prime factorisation?
We know that all non-prime (or composite) are a product of primes. Prime factorisation of a number n is finding what primes multiply together to make up n and how many times.
For example:
Computing a prime factorisation
We can compute the prime factorisation of a number using a fairly straightforward approach. Let n be the number of which we want to compute the prime factorisation. All we have to do is search all its possible divisors, much like the approach I presented during the first article about prime numbers, with a slight modification: when fiding a divisor, we will divide n by it as many times as possible. This will guarantee us that we will only divide n by its prime factors: let us suppose we found a composite divisor d of n; then, any number in the prime factorisation of d (implicitly smaller than or equal to d) is also in the prime factorisation of n, which can only be true for d, as all its prime factors should have already been handled. That would imply that d is prime, resulting in a contradiction.
We can skip even numbers as they will all be multiples of 2, which we will test separately, resulting in the following implementation:
void primeFactorisation(int n) { /// suppose n is >= 0
if(n <= 1) cout << n << ' ';
else {
/// firstly, we will test n separately.
int p = 0; /// p will store the power of each number in the prime factorisation of n.
if(n % 2 == 0) {
while(n % 2 == 0) {
n /= 2;
p++;
}
cout << "2^" << p << "; ";
}
/// now we will search the possible divisors of n for prime factors.
for(int d = 3; d <= n; d += 2) {
if(n % d == 0) {
p = 0;
while(n % d == 0) {
n /= d;
p++;
}
cout << d << "^" << p << "; ";
}
}
}
}
It is obvious that, for large numbers, a vast amount of non-prime numbers would be tested as well. If we were to compute multiple queries asking for the prime factorisation of n, we could use The Sieve of Eratosthenes, described in the previous article to precompute the primes up to a given limit and then, instead of searching for the possible divisors of n for the prime factors, we would only search for divisors of n across the precomputed prime numbers.
Why computing prime factorisations interest us
In my first article about primes I mentioned that [RSA](https://en.wikipedia.org/wiki/RSA_(cryptosystem), the most common encryption tool today makes extensive use of prime factorisation by using a private key which is the product of two big prime numbers. In theory, you can crack any RSA private key if you ran a modified version of the algorithm I wrote above. In practice, you do not have the time to do that. The time taken to compute the prime factorisation of a sufficiently large number is non-polynomial, and there is no known polynomial algorithm (running on a classic computer) to compute this prime factorisation.
The latest RSA standard to be factored is RSA-240 in November 2019. For reference, computing this on a 2.1 GHz Intel Xeon Gold 6130 would take 900 years.
That's it for Primes: Fast and Slow. I will be updating this series of articles (and some others!) with various computer science stuff regularly, so feel free to follow me if you haven't already to keep in touch with it.
If you liked this article, you may like other articles I have written:
Top comments (0)