Prime Numbers In Cryptography

Introduction

A central notion of elementary number theory is Prime Number. Prime numbers are used in many cryptographic algorithms, particularly in RSA (see how to generate key pairs using prime numbers), which is one of the best public key (asymmetric key) cryptography algorithms. In this article, I am going to introduce prime numbers, illustrate how every positive integer is a product of prime numbers and demonstrate how prime numbers are used in cryptography.

Prime Number Definition

An integer p > 1 is called a prime number if it has exactly two positive divisors, namely 1 and p itself.

For example, the first seven prime numbers are 2, 3, 5, 7, 11, 13, 17. Note that 2 is the one and only even number.

An integer a > 1 that is not a prime number is called composite.

Important Theorems

If the prime number p divides the integer a, then p is called prime divisor of a.

Theorem 1. Every integer a > 1 has a prime divisor.

Theorem 2. Every integer a > 1 can be written as the product of prime numbers, which is called a prime factorization of the integer number a.

For example, 70 = 2 * 5 * 7, where 2, 5 and 7 numbers are called prime factors. Note that the same prime factor may occur more than once. For example, 315= 3 * 5 * 7 * 3; this example has two copies of prime factor 3.

Prime Numbers & Cryptography

The prime factorization of an integer number a > 1 is the representation of a as the product of prime numbers. The mathematical problem of finding the prime factorization of an integer number is called the integer factorization problem. Efficient algorithms for finding prime factors are not known. This fact is the basis of the security of the RSA algorithm and other important cryptographic algorithms or systems. There is also no proof that the integer factorization problem is difficult. To prove that a given positive integer is a prime number is expensive and in many cryptosystems large prime numbers are used. There are algorithms that prove the primality of a positive integer number, such algorithms are called primality tests.
It is quite possible that in the future someone will solve this problem and/or invent an efficient integer factoring algorithm. If someone solves the problem related to the cryptographic systems, it will need to be based on the difficulty of integer factorization that is insecure and thus must be replaced by others.

P.S.
January 3, 2018: Great Internet Mersenne Prime Search announced that a computer owned by Jonathan Pace in Germantown, Tennessee, USA, discovered the largest known prime number, having 23,249,425 digits, also known as M77232917.

If you have learned something new, please share and recommend this to allow others to learn too!