Computer science Journey into cryptography Primality Test 2 articles 5 programs 8 videos Why do primes make some problems fundamentally hard? To find out we need to explore primality tests in more detail. Introduction 1:05 Primality test challenge How can a machine tell us if a number is prime? Trial division 5:24 What is computer memory? What is the limit of computer memory? 8:42 Algorithmic efficiency How can we improve the speed of a (deterministic) primality test? Level 3: Challenge Try and improve the efficiency (time complexity) of you algorithm A so that it beats algorithm B in the worst case 4:12 Sieve of Eratosthenes Sieve of Eratosthenes allows us to generate a list of primes. Level 4: Sieve of Eratosthenes Sieve of Eratosthenes 5:22 Primality test with sieve An attempt at an optimal trial division primality test using the Sieve of Eratosthenes. Level 5: Trial division using sieve An attempt at an optimal trial division primality test using the Sieve of Eratosthenes. 6:46 The prime number theorem How can we estimate the number of primes up to x? Prime density spiral Explore the distribution of primes Prime Gaps Graph of the spaces between prime numbers 6:34 Time space tradeoff what is our memory limit? How can save time at the expense of space? 7:04 Summary (what's next?) Why is factorization hard, yet generating primes easy? Where do we go from here?