Why are prime numbers so important in encryption?

Why are prime numbers so important in encryption? Considering that there is many ways of finding these numbers, even very big ones and "paper and pencil" systems are extremely fast (all pure integer maths) with very big numbers, it seems odd.

Or have I got it wrong somehow?
LVL 40
Richard QuadlingSenior Software DeveloperAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Prime numbers are used in assymetric encryption.
The complexity of some solving some mathematical problem in one direction as opposed to the simplicity of the operation in the other direction makes it suited for assymetric encryption.
The factoring of prime numbers is one of those complex problems. Others are
It's very easy to calculate two prime numbers and multiply them. Factoring that large number back to the two primes is extermely hard.
So, the public and privare keys are made up from a pair of large prime number.
As long as noone finds an easy way to factor into primes, then it stays safe. That may change in the future.
A practical algorithm using this is RSA. Have a look here how it is done: http://world.std.com/~franl/crypto/rsa-guts.html
Or more detailed: http://en.wikipedia.org/wiki/RSA


Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
Been a bit to fast. Some typos above, my apology.
Other examples of such complex problems are the calculation of discrete logarithms in a finite field, elliptic curves and the knapsack algorithm.

Richard QuadlingSenior Software DeveloperAuthor Commented:
Aha! I see. I think.

Cloud Class® Course: C++ 11 Fundamentals

This course will introduce you to C++ 11 and teach you about syntax fundamentals.

Prime numbers are very hard to find. Although you can find some with pen + pencil methods, when the numbers have hundreds of digits there is no known way to find them. It takes a huge amount of processing power to factorize them as it must be done through brute force
Richard QuadlingSenior Software DeveloperAuthor Commented:
Hackman_3vilGuy, but there are lists of these numbers and a lookup on a list is pretty quick.

The problem is that there are an infinite number of prime numbers in the universe so a list of all the primes at the sizes used by governments are completely infeasible. At 4096+ bits it is pretty impossible.
Remember the bank / government / whoever will generate 2 prime numbers p and q that can be as big as they want. They then multiply them and publish n which is p * q. So the attacker has p*q, but to decrypt the message needs to know what p and q are separately. There are methods that speed this up but they dont improve much over brute force. Not only is it hard to factorize them as there is no mathematical formula, it is hard to generate the primes to test with in the first place. RSA encryption (used online) relies on the difficulty of factorizing these gigantic prime numbers as well as another difficult problem (the RSA problem).

As of 2005, the largest number factored by a general-purpose factoring algorithm was 663 bits long, using a state-of-the-art distributed implementation. RSA keys are typically 1024–2048 bits long. Some experts believe that 1024-bit keys may become breakable in the near term (though this is disputed); few see any way that 4096-bit keys could be broken in the foreseeable future.

the complexity is not in finding primes, but in factoring TO primes of the multiplication of two primes.
So given a large number find the two originating primes.

Richard QuadlingSenior Software DeveloperAuthor Commented:
OK. Getting factors of a number is hard enough. Getting prime factors of the product of two large primes does sound sort of ridiculously hard. But not impossible.

Whilst brute force is slow, you would only need to run this once.

http://en.wikipedia.org/wiki/Largest_known_primee - the largest prime is just under 10 MILLION digits long!!!

Say the next one is 11million digits long.

The product is going to be over 20 million digits long.

Now find the factors and only the PRIME factors.

And that's why.


Thanks for all of that.

I bet all those botnets out there could be useful if all they were doing was calculating primes rather than sending SPAM.

Thanks again all.

It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today

From novice to tech pro — start learning today.