If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

### Course: Computer science theory>Unit 2

Lesson 4: Modern cryptography

# RSA encryption: Step 3

RSA Encryption (step 3). Created by Brit Cruise.

## Want to join the conversation?

• I've heard quantum computing has the potential to do prime factorization very easily. If quantum computers become a reality, will this spell doom for encryption as we know it? What will happen then?
• 1. Click 'explore this concept' in top right corner to interact with graph used in video.
2. Still curious why factorization is hard? Watch this next http://www.khanacademy.org/math/applied-math/comp-number-theory
• what does "size of imput" means on the "explore this concept" page?
• Around Brit says that it's really hard to figure out the factorization of the 300-digit number if you use two 150-digit numbers. But if the person trying to find the factors KNOWS that you're multiplying primes together to generate those long numbers, couldn't they just limit their brute-force search to prime numbers? In other words, when looking for the factorization of the 300-digit number, couldn't they just try multiplying different primes together to see what they get? That would seem to greatly reduce the amount of time it would take to figure out what factors were used to generate the 300-digit number.
• Saying "factorization" in this context means "prime factorization". And such knowledge will not help to break encryption in a reasonable time, anyway. There is still huge number of combinations to search.
• How long would it take to generate a random prime number over 150 digits long? And how would you even go about generating said prime number??
• How long it would take depends on what kind of computing power you have and how you use it. The latter - the algorithm/method - is more important than the computers used.
• As far as prime numbers are concerned, are they a result of our base 10 system? or are the prime numbers consistent throughout different bases?
• That's a really good question; great thinking! Don't think of primes as being only for mathematicians - think of them in terms of things, like seeds or coins. No matter what base you are in, the point is to assign a value to a certain number of things - humans use base 10 because we are used to that since we have 10 fingers (according to the anthropologists, anyway). Base 60 was also common in ancient times, but the end goal of any number system is to assign a value. No matter what base you are in, there will be some values that cannot be split evenly between a certain amount of people - this is easily visualized. If you have 5 things, you could say 5 or 0101, but in the end, you wouldn't be able to divide those things evenly between 2 (10) people. What makes prime numbers special is that they can't be divided evenly between any number of people except that number, or if one person takes them all. Especially if the things in question are cookies. Then they're mine. The only thing that really changes between bases is the arithmetic and algorithms involved in finding primes - dividing multiple times in anything but base 10 makes my head hurt. Hope this helped!
• When you click on 'explore this concept' it shows the factorization estimating thing.

How does it estimate how long a factorization will take without doing it?
How much CPU does it assume?

thanks
• It's just an estimation using a formula/table of stored value, it doesn't actually perform the factorization. It is based on a modern, though fairly slow, single CPU
• What was that website at ?
• What is the website that calculates time needed to multiply or factorize and plots values on the graph? I need an answer as soon as possible!
• couldn't you just run through primes that were roughly the right size? also, why not use squares and SQRTs, since you have to guess to get those too?