Prime Numbers and Cybersecurity

A NP Problem

Prime numbers are whole numbers that can only be divided by themselves or one, and they are used in our every day lives through encryption and cybersecurity.

Multiplying two prime numbers, even if the numbers are very large is “easy” by easy I mean, it can be solved and verified in polynomial time or O(n^k) in complexity theory, which puts this problem in class P. In computational complexity theory, class P contains all decision problems that can be solved and verified in polynomial time, some other known problems in the P class would be finding the greatest common divisor (GCD) and determining if a number is prime or not.

Unlike the example below “41 x 11” , computers use extremely large prime numbers to multiply together.

 41 x 11 = 451

However finding the prime factorization is “hard” by hard we mean there is no known solution in polynomial time or is currently Little-Omega(n^k) in complexity theory, which puts this problem in the NP class. Although it may not seem hard to figure out the two prime numbers that…