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

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?

Or have I got it wrong somehow?

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with Premium.
Start your 7-day free trial.

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.

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 trialOther examples of such complex problems are the calculation of discrete logarithms in a finite field, elliptic curves and the knapsack algorithm.

J.

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.

J.

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.

Ok.

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.

Richard.

Encryption

From novice to tech pro — start learning today.

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with Premium.
Start your 7-day free trial.

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

J.