Main content

## Computer science

### Unit 2: Lesson 6

Primality test- Introduction
- Primality test challenge
- Trial division
- What is computer memory?
- Algorithmic efficiency
- Level 3: Challenge
- Sieve of Eratosthenes
- Level 4: Sieve of Eratosthenes
- Primality test with sieve
- Level 5: Trial division using sieve
- The prime number theorem
- Prime density spiral
- Prime Gaps
- Time space tradeoff
- Summary (what's next?)

© 2023 Khan AcademyTerms of usePrivacy PolicyCookie Notice

# Introduction

Have you seen the lesson on Modern Cryptography? At the last checkpoint this was the most popular question asked by users:

In the lesson we saw how prime factorization played a fundamental role in the construction of

**mathematical locks**. A mathematical lock (or

**one-way function**) requires a procedure which is

**easy to perform and hard to reverse**.

For example, If I

**randomly pick two large prime numbers**such as:**P1 = 709**and**P2 = 733**and multiply them to get:

**N = P1 * P2****N**= 709 * 733 =

**519697**(this is

**easy**to compute)

I end up with two things: a large number (

**519697**) and the prime factorization for that large number (**709 * 733**)Now, imagine I

*hide the prime factorization*and only provide you with the following:**519697 = ? * ?**(this is

**hard**to compute)

If I ask you to

**find the prime factorization,**where would you begin? Don't worry, everyone would struggle with this problem! To find the solution you must do a bunch of trial and error tests.**Multiplication is fast (easy) to compute while prime factorization is slow (hard)**. This simple fact forms the basis for the RSA encryption scheme.👁️ Watch this animated graph to see the difference.

Though before going any further, we need to zoom in on the first step and ask ourselves an important question. When we say

**"randomly pick two large primes"**, how do we do this quickly?**Is it an easy problem?**If you think about it for a while, you'll eventually agree that this step requires, at minimum, the ability to

**check if a randomly generated number**(such as 99194853094755497)**is prime or composite**. Do you have a button on your calculator to tell you this?I don't see one….

**Why is this?**

To find out, let's begin with a challenge...

## Want to join the conversation?

- why is 1 not a composite or prime number(25 votes)
- Mathematicians now consider 1 to not be prime because it is inconvenient if it is prime. Believe it or not, back in the 19th century some mathematicians did consider 1 to be prime.

If 1 is prime it breaks the**Fundamental Theorem of Arithmetic**which says that all numbers >1 have a unique prime factorization. (The prime factorizations would no longer be unique if 1 was prime)

e.g.

If 1 is not prime the prime factorization of 6 is 6=2*3, and it is unique.

However, if 1 is prime then we could also have the following prime factorizations of 6: 6=1 * 2 * 3, 6=1 * 1 * 2 * 3, 6=1 * 1 * 1 * 2 * 3, etc. The prime factorization of 6 would no longer be unique.

The**Fundamental Theorem of Arithmetic**is a useful tool in mathematics, so mathematicians decided to exclude 1 from being prime. The biggest benefit to this, is that 1 doesn't have to be considered as a special case every time we prove something (This saves a lot of paper and even more headaches).

Hope this makes sense(99 votes)

- A "prime/no prime" button
*would*be pretty nice to have, now that I think about it...the calculator is capable of computing some pretty advanced calculations, why can't it tell if a number is prime? Even if it takes a while, it would be useful to know...(15 votes)- While a prime/not prime button would be cool, there are some logistical difficulties with putting it on a calculator. Most primality testing algorithms in use today are based on probabilistic principles. For example, the Miller-Rabin Primality test can definitively tell you that a number is not prime, but can only tell you with very high probability if a number is actually prime. The reason is that the algorithm (which is an amazingly elegant piece of mathematics) tests a given input for "strong pseudoprimality" i.e., it checks whether your input satisfies a series of conditions when paired with a randomly chosen number, like 2 or 3. If you run the algorithm 50 times with 50 random numbers, then the probability that your number (of less than 200 digits) is prime is greater than 99.99%. So you might ask: is there a completely deterministic test for primality? That was discovered recently by two undergraduates (and their advisor) in 2000. It answered a fundamental question, but the algorithm is way too slow to be of any practical use. So coming back to your calculator, they usually feature deterministic algorithms, and primality testing, at least at a basic level, does not conform to that.(20 votes)

- ok i really dont understand prime numbers cant any one help me?(4 votes)
- A prime number is a number that can only be divided by only the number one and itself.

Such as: 7 is a prime number because it can only be divided by 1 and 7.(8 votes)

- Are negative numbers prime or composite? Are their structures similar to positive numbers?(2 votes)
- That's a good question! Negative numbers are neither prime nor composite. (The same applies to 0.)

The question of "is it prime or composite" only applies to numbers greater than 1. It doesn't apply to 0 or 1, or negative numbers, or fractions, or ducks, or airplanes.

Negative numbers do have a similar structure to positive numbers; for example, a negative number (less than -1) can always be factored into -1 times some primes.

At this level, mathematians start dividing numbers into several different kinds. They talk about the kinds of numbers that can count how many things there are (which are called cardinal numbers; there's 0, 1, 2, or 3 apples), or positions in a list of things (called ordinal numbers; this apple is the first, second, third, etc); cardinals and ordinals are the same kinds of numbers until you deal with infinities. They start talking about kinds of numbers that can be fractions of integers (rationals), or kinds of numbers that can talk about the differences of two other numbers (integers). That last kind of numbers is where negative numbers come in. Talking about negative numbers doesn't make sense when you're talking about cardinals or ordinals; you can't have negative three apples!

When mathematicians started talking about these different kinds of numbers, they also realized that some definitions only apply to certain kinds of numbers. So talking about a prime number meant you were only talking about positive (or "natural") numbers; it didn't make any sense to talk about negative primes, or fractional primes, or anything like that.

So that's a great question: negative numbers aren't prime, and aren't composite; they're a different type of number than those definitions apply to. And their structure is similar to, but different than, positive numbers.(7 votes)

- But my calculator
*does*have an equivalent function for primality tests. It is actually factorization. I used to use CASIO fx-350ES PLUS, and when I click SHIFT-degree (º ' "), which on the above calculator is actually "←," I get the factorization of the number currently in the answer section. If the number is prime, the calculator displays the number in parentheses. (By the way, for 1337 I get 7×191; and when I factor 1 or a non-positive integer or fraction, I get a Math ERROR.)

On a TI-Nspire CX, I press menu-2(Number)-3(Factor), or I type in "factor(" and I get the factoring function. It can also "factor" negative numbers and fractions, and when it can't factor a number (1, 0, decimals, irrationals, imaginary numbers) it displays the original number (simplified).

In fact, the calculator in the picture is the first scientific or graphing calculator I've seen that definitely doesn't have a factoring function. Of course, It's probably because I never look closely at other people's calculators.(3 votes)- Good point! Many modern scientific calculators have a "factor" function, and usually have since the early 90s. In fact, many of them will actually test to see if a number is prime before factoring it. For example, my trusty HP 50g will mark the number 99,194,853,094,755,497 as prime immediately, but if I try to factor 99,194,856,159,718,057 (the nearest semiprime), it runs for about a minute and a half before giving up.

The main point that the lesson is this, though: it's a lot easier to multiply primes to get a number, than it is to factor a number into its primes! I hope the next two lessons make that clear.(4 votes)

- The calculator says 1337 or 'LEET'.......Coincidence or are you part of the tech elite?(3 votes)
- *What is the biggest prime number?*(2 votes)
- Say we have found the biggest prime number... let us call it P.

Then let us take P! and subtract one. Since P! is divisible by all numbers up to P, P! - 1 cannot be divisible by any of the numbers up to P excluding 1. So we have either found a prime number bigger than P or there is another prime number largest than P that divides into P! - 1. Either way, our statement that P is the largest prime number is contradictory. And therefore we have proved by contradiction that the "biggest prime number" does not exist. Primes continue on forever.(3 votes)

- I am making a program that you input a number and it tells you whether it is prime or composite. Can you find some big primes for me to test with?(1 vote)
- Why is 2 the only even prime number?(0 votes)
- By definition, any even number larger than 2 will be divisible by 2. Thus it cannot be prime.(3 votes)

- there is only unique prime factorization for a given number. If we main prime factors for all the numbers in a map. isn't it easy to solve the problem with O(1) complexity?(1 vote)
- Yes, and that's usually how you would do it for simple problems. This approach just doesn't work for larger numbers (because maps take up space)(1 vote)