Semi-Prime Number Originator Lookup For Identifying Prime Numbers

139 Views Asked by At

In one of BBC's documentaries on security, a mathematician stated that prime and semi prime numbers helped with the design of RSA encryption - a number like 91 can be easily calculated through multiplication with two prime numbers 7 and 13, but its opposite operation (division) takes more effort, especially as we have larger and larger semi-prime numbers made up from prime numbers.

For reducing the complexity of calculating the opposite operation (division), what stops attackers from using a mathematical approach of using a lookup system of all semi prime numbers and their origins? In other words, rather than trying to find the two prime numbers that make a semi prime number through multiplication, have a lookup of every semi prime number and the prime numbers that made it up?

This changes the mathematical complexity from a problem of trying to find the prime numbers that create a semi-prime number to finding the semi-prime equal value in a list and then getting the prime numbers.

1

There are 1 best solutions below

1
On BEST ANSWER

There are approximately $3.9 \times 10^{97}$ primes of $100$ digits, and approximately $7.6 \times 10^{194}$ semiprimes formed from those primes. The visible universe only has something like $10^{80}$ protons (the Eddington number), so a supercomputer composed of all the matter in the visible universe wouldn't come anywhere near being able to store all of these primes, let alone all the semiprimes.