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

Current time:0:00Total duration:5:06

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 and it will never label it as composite however if n is composite then there will be some tiny chance of error e that it will label it prime otherwise there is a one - this tiny error probability that it will correctly identify it as composite so we'll start simple out of some universe of integers up to some limit we grab a number and call this integer N and we input n into our machine and previously in our trial division methods we basically iterated through all values from 1 to the square root of N and test it if that number divides in and ideally we only wanted to check Prime's to save time and if yes a divides n then we know that N is a composite number because we found a composite witness if not then we aren't sure so we go back and we increment a and we test again and once we exhausted all possible tests we could then say yes and is prime if we found no divisors but 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 since we know that some number n if its composite it must have some divisors scattered around and at minimum it has a single divisor and some composite numbers have many divisors so anyway we pick a random integer a between 1 and the square root of N and that's it then we just check if a divides n and as before if a divides n then we know for sure that n is composite we found a witness if not then we haven't learned too much except that it could be prime so to be safe we could generate a few more random a's and keep testing and perhaps after a hundred or a thousand iterations we could stop and say it's probably prime with some certainty say for example 99.9 percent and 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 five heads we are more than 90% sure so we could stop and say oh we think the coin is two-headed so here is a program I've set up which compares our old trial division methods with this new random division test and I'm specifically using the current trial division speed leader which is a program by Dino and I posted the link in the header of the program so to begin notice the variable number of trials this is the number of random guesses so we'll start at something small such as 3 and notice even with small input if the input is prime the random division algorithm will always output prime but when the input is composite we see the random division can make mistakes and identify it incorrectly as prime however we can fix this by increasing the number of trials and then the probability of an error goes down and we see now that the outputs more or less match and as I test larger input the error grows again so I need to increase the number of random tests accordingly and when I do the outputs match very nicely they seem identical but with huge input size I need thousands of random tests for this to be accurate so we haven't actually improved the number of steps needed our trial division method still seems better this is because the error rate of the division test is so high but we are close we have the right idea so 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 and 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