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.

Main content

Random primality test (warm up)

Introduction to random primality tests & how they will work (warm up). Created by Brit Cruise.

Want to join the conversation?

  • Is there any function to find out exactly what the chance of error is with a certain size number and a certain number of random tests?
    (21 votes)
    Default Khan Academy avatar avatar for user
    • piceratops ultimate style avatar for user Max
      No, there is no such algorithm. The accuracy of a probabilistic primality test in dependent on the underlining mathematical framework. Thus the accuracy varies from test to test. However, the accuracy of the primality test does increase as the number of trials increases. Additionally, the size of the number should not matter as long as the number of trials increases to account for the larger search space.
      (8 votes)
  • blobby green style avatar for user saoudakram.ge1201
    Hello! I loved your series of videos on Cryptography! Thank you so much for all that work! Is it possible to make a few videos on "Quantum Cryptography"?
    (6 votes)
    Default Khan Academy avatar avatar for user
  • old spice man green style avatar for user Kerr, C
    is this kahn he sound different
    (0 votes)
    Default Khan Academy avatar avatar for user
  • leaf red style avatar for user erichspaker
    why do you want the algorithm to always output primes as prime, and occasionally mistake composites for being prime, instead of the other way around, such that numbers output as prime are certainly prime, and the algorithm sometimes misses primes (outputting them as composite)
    (3 votes)
    Default Khan Academy avatar avatar for user
  • female robot grace style avatar for user Anna
    I have heard that generating primes is easy but that requires at minimum a trial division test which has the same runway effect as factoring composite numbers so how can generating primes possibly be easy?
    (2 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      Generating prime numbers is easy (defined as within polynomial time, which in simplified terms means the time to do it doesn't grow exponentially as the size of our numbers increase).

      The basic idea is:
      -Step 1) pick some random number
      -Step 2) use a test that tells us with some % chance P that the number is prime
      -Step 3) if the test says the number is not prime we reject it and start over at Step 1
      -Step 4) if the test says it may be prime we repeat steps 2 and 3 several times until it is very unlikely that a number that wasn't prime could have survived all of the tests
      -Step 5) we declare the number probably prime and use it as a prime number

      In recent times (2002) some very clever folks came up with a deterministic method (doesn't rely on chance) that can replace steps 2-5. It is called the AKS algorithm. While it is very interesting most people still use the probabilistic method.

      http://en.wikipedia.org/wiki/AKS_algorithm

      Hope this makes sense
      (2 votes)
  • blobby green style avatar for user tnichols9178
    This is so fun to be learned
    (2 votes)
    Default Khan Academy avatar avatar for user
  • starky tree style avatar for user Md Tareque Khan
    Where is the link to play around with the guessing the primality of a number using number of iterations? The one discussed in this video.
    (1 vote)
    Default Khan Academy avatar avatar for user
  • leaf orange style avatar for user vefmur
    Would this work; factor a, then divide n by each of the factors?
    (1 vote)
    Default Khan Academy avatar avatar for user
  • male robot johnny style avatar for user Noam-Dimitri Monárrez Lachhein
    What does the symbol ++ mean? Is some kind of another math or programming?
    (1 vote)
    Default Khan Academy avatar avatar for user
  • leaf blue style avatar for user x y
    Why does the trial division only use 2 steps? I though it would check as many numbers as are determined in the variable numTrials.
    (1 vote)
    Default Khan Academy avatar avatar for user

Video transcript

Voiceover: First, let's build up the conceptual mechanics for these new types of random algorithms which accept some input N and if N is prime, our algorithm will output prime with 100% certainty. It will never label it as composite. However, if N is composite, there will be some tiny chance of error E that it will label it prime. Otherwise, there is a one minus this tiny error probability that it will correctly identify it as composite. We will start simple. Out of some universe of integers up to some limit, we grab a number and call this integer N. We input N into our machine. Previously, in our trial division methods, we basically iterated through all values from one to the square root of N and tested if that number divides N. Ideally, we only wanted to check primes to save time. If yes, A divides N, we know that N is a composite number because we found a composite witness. If not, we aren't sure. So, we go back and we increment A and we test again. Once we exhaust all possible tests, we can then say yes, N is prime, if we found no divisors. Now, let's be lazy. What if we just pick a few random integers and do a few divisibility tests which you can think of as random questions. We know that some number N, if it is composite, it must have some divisors scattered around. At minimum, it has a single divisor. Some composite numbers have many divisors. Anyway, we pick a random integer A between one and the square root of N. That's it. Then we just check if A divides N. As before, if A divides N we know for sure that N is composite, we found a witness. If not, we haven't learned too much except that it could be prime. To be safe, we could generate a few more random As and keep testing. Perhaps after 100 or 1,000 iterations, we could stop and say "It's probably prime" with some certainty. Say, for example, 99.9 percent. This is similar to the example game on conditional probability. In the simplest version, we were trying to guess if a coin was fair or if it was a two-headed coin. In this case, tails is like finding a divisor. It's a witness of a fair coin. Heads is the case where we might want the person to flip again and iterate. In this case, after around 5 heads, we are more than 90 percent sure so we could stop and say "We think the coin is two-headed." Here is a program I have set up which compares our old trial division methods with this new random division test. I am specifically using the current trial division speed leader, which is a program by Dino. I posted the link in the header of the program. To begin, notice the variable number of trials. This is the number of random guesses. We will start at something small, such as three. Notice, even with small input, if the input is prime, the random division algorithm will always output prime. When the input is composite, we see the random division can make mistakes and identify incorrectly as prime. However, we can fix this by increasing the number of trials then the probability of an error goes down. We see now that the outputs more or less match. As I test larger input, the error grows again. I need to increase the number of random tests accordingly. When I do, the outputs match very nicely. They seem identical. With huge input size, I need thousands of random tests for this to be accurate. We haven't actually improved the number of steps needed. Our trial division method seems better. This is because the error rate of the division test is so high, but we are close. We have the right idea. We need to use another test. We need an equation which is fast to calculate, that can be used to prove whether a number is composite. It must accept not only the input integer N, but also a random integer A and do a random test in the same sort of way.