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.

# Summary (what's next?)

Why is factorization hard, yet generating primes easy? Where do we go from here? Created by Brit Cruise.

## Want to join the conversation?

• does it take the same amount of time for a computer to calculate 7+4 as to 700+400?
if not how does it differ?
• Yes it takes. One fundamental reason to this would be that you can express 7 and 4 with 3 bits but you need 10 bits for 700 and 9 bits for 400.
This means a longer stream of bits must pass through transistors to make the calculation.
This difference is insignificant, like really insignificant.
• cant people find a prime by first finding another prime,n, and then finding (2^n)-1?
(1 vote)
• Nope. The number 2047 ((2^11)-1) factors to 23 * 89. This approach is seductive, because the first few primes do generate more primes, but as n becomes larger, the resulting numbers are usually not prime. These numbers are known as Mersense primes. More about them at http://en.wikipedia.org/wiki/Mersenne_prime.
• Instead of defining the step size by using prime numbers, can we use other well-known sequences that may also work, such as Fibonacci numbers or any sequence that meets Brown's Criterion?

Also, will there be videos on primality test other than trial and Sieve?
• The Random algorithms lesson will explore new ways of performing primality tests. The Rover is just used as a practical example throughout the lesson (the limitations of the rover's computer are similar to the limitations of our web browser)
• Any chance of getting videos on pollard's p-1 and rho algorithms? How about the Chinese Remainder Theorem? Also something on WEP and why it's so easy to break. Keep up with this awesome series!
• Thanks for the advice/feedback Richard. WEP is coming soon and Chinese remainder is also on the TODO list. Won't be posting updates for a few months as I'd like to finish information theory first
• Is P=NP related to time complexity?
• Yes. The P in P=NP means polynomial. Essentially they are categories for algorithm running speed. Do of the broadest categories are polynomial time and non-polynomial time. Multiplying two numbers is considered a problem that can be solved in polynomial time. There is no known factoring method that is polynomial time. If P=NP is proved true it would mean that anything that can be done in polynomial time can be done in reverse, in polynomial time.
• What was the largest prime number ever found?
• You can Google it. It has approximately 17 million digits.