Video 9-6: Primality testing

0:03 In the next section, I want to come to visit a problem that is almost as old as algorithms are, but also one that specifically randomization uh has a has a key role to play in. Um that's the question of deciding whether a number is is prime. Before we'll come to that uh a few comments on the design technique that underlies the algorithm we'll look at and that's this um a forementioned abundance of witnesses. Uh so again framed it again bit from the the complexity theory perspective if you have some language in NP then you know there must be some certificate for every word in the language that uh certifies that that's in the language. Um if we have that certificate at hand then it's uh it must be efficient to check. Um now in general this is not always true for for everything uh in in NP but uh suppose that it is true for our specific language that there are many certificates that actually show that X is in the language.

1:12 Um, that's an assumption we're making here, but we'll see examples. If that both is true, then it it makes sense to try to just randomly guess some string and check if it is a certificate. Maybe we're lucky and uh then we'll quickly prove that X is in L. And if we've kept going for a while and we couldn't find any certificate, then maybe we can conclude X is not in the language. Uh, that's the idea in abundance of witnesses. uh you hope you have a language in NP where there's many certificates and so either you find one or if you don't find one um there's a good chance that there there is none. So the input is not in the language. Um and let's apply that to um a more concrete problem. So given some number n all we want to know is is that a prime number or not? Um it can be traced back a lot in time.

2:09 People wondered about this for a long time and it's only fairly recently been properly resolved in a way. Uh let's first look at some some simple approach that you've probably seen in some introductory classes up in a good intro algorithm. How do we define how do we find out if a number is prime? Well, if we've tested all potential factors and none of them divided the number, then clearly it is a prime. And more specifically we can test all prime numbers below square root of n. These are the only actual candidates for for uh well the only interesting candidates for for factors. Uh the number might have more factors but if it has any factors it will have one of those a prime number below square root n. Right? uh square root n is is clear any factor will be either below square root n or div number divided by the factor is below square root n. So checking for one of the two is enough and we can restrict the attention to primes because if there's a non-prime then it has a factor and then we could have well taken that factor instead.

3:20 But in a way this sounds like uh we're we're trying to solve the problem by solving it's the same problem. uh which sounds a bit contradictory, right? We need to know what a prime we need to know primes to check if a number is prime. Uh but of course there's no no contradiction because you can do an inductive algorithm and in particular there's a clever algorithm you will have seen the se of eratosinus which gives you all the prime numbers up to a certain threshold in a somewhat reasonable running time overall. And here's the algorithm itself. It's basically uh it's called a seie because it goes through all the numbers and kicks out those that are composite that are clearly not prime and it effectively goes through the numbers from small to large and then crosses out all multiples of a number. You can be a little smarter. So first of all um you iterate over the numbers but then if you already know that a number is prime then you have to do it. Otherwise you don't because you'll have a factor that already crossed out all your multiples.

4:25 And also with the multiples you can start at the number itself. So you start with a square of the number because all smaller multiples will have been caught by the smaller multiple as a number. Uh think about it for for a minute and you'll you'll see why. So that's where we can start and we go up to um a point where we would overshoot n and then we take the the m the product the multiple of i and mark that as not prime and then we uh if if we've done all that everything that is left must be a prime number. So that's finding primes up to a threshold. Uh if we want to test a number for primality, what we do is we compute all the prime numbers up to square root of the number and test all of them. Easy. Uh how good is this? Um the time of the primality check clearly is dominated by finding the primes. And how how long does that take? Uh is actually a subtle analysis um if you want to be precise. So the time to find all the primes up to number m is well m for going through the loop uh the outer one um sorry for yeah up to n but I'm I'm setting m is square root n so you go through this loop m times roughly and then for each prime you have to go through that many iteration of the inner loop I'm kind of not analyzing these starting at i part uh that one is is a clever trick, but I'm I'm just ignoring that here. So, it's just an upper bound.

6:06 But doing this sum where you have to do a summation where you only do the prime factors, that's that's tricky. Uh so, we can make our life easy and get an upper bound by dropping that restriction and then at least you get harmonic numbers. So, m log m time sounds not too bad if you write it that way. And uh if you do actually make the analysis more careful and take into account that you only have the prime numbers here, you can show that it's m log log m really uh that that seems to be more technically involved. So we're not going to do it. Uh and the space of course is maybe practically speaking more of a problem. Now all of this sounds okay, right? Uh m log m we've we've been happy with algorithms of that running time. But of course the problem is here that this is a number and we would encode that in binary. So even even square root n is an exponential in the actual input size.

7:04 And um I think if you take this primality check and apply it to prime numbers as you would use them in cryptography, it's not going to be good enough. You need some smarter techniques. Okay, but that's kind of the uh the trivial algorithm to do it would work like this. And it's not completely useless, but uh um it's it's going to be uh exponential in the input size. So the question um then quickly comes up, can we do much better? What's the uh complexity status of these problems? And so with these problems, I've not defined the problems. Let's do that here. There's two problems. There's the problem primes. Um if you think about a language, that's the set of numbers that are prime. So we're given an integer in uh in binary and we want to check yes, no, is that a prime number? Um, and you can also use the search problem of this decision problem, the integer factorization problem, uh, where you're given an integer, but then you either want to find some non-trivial factors which prove that the thing is not prime, uh, or you output it's not prime, it's prime, in which case we don't require a certificate in the problem of integer factorization.

8:30 Okay. Um as you may uh see from this immediately if the number is is not a prime then uh the factorization is a certificate. So we can conclude that primes is in co-enp because the no instances have an uh an efficiently checkable certificate. Uh what's not clear is if the yes instances also have a certificate. How would you prove to me that a number is prime other than saying I've tried all the factors and none of them is a is a I've tried all the numbers and none of them is a factor. Uh that seems seems less clear. So whether primes is innp is already a bit unclear from just from the definition. Um also a good point to make the connection to the very far beginning of the lecture. The running time of of the se of aeritos is of course pseudo polomial right it's a it's polomial in terms of the number of things in the input but it's uh is only pseudo polomial if you take the binary encoding.

9:47 Now what we'll show is uh a slightly u better result. uh so here the fact that it's in co-enp is not practically useful right we don't expect efficient algorithms for all problems in co-enp for NP uh but we'll show that you can do a randomized test a randomized uh primality test or compositionality test I should say um which also shows that the problem is in BPP and we've already seen BPP is likely to be the same as Now in this case uh we don't actually need to invoke these kind of arguments. If you're just curious about the complexity status um it's been in this millennium but a while ago by now um as a major breakthrough we now know now deterministic unconditional algorithm that runs in polomial time and decides whether a number is prime and there's also a notion of certificate in a way that uh the algorithm can prove to you that a number is prime uh without just exhaustively going through all factors and showing that these are not fac numbers and showing that these are not factors. Uh this clever number theory behind it. Um crucially this is not clear for integer factorization and everyone working in cryptography knows that the classic cryptography really relies on factorization being hard.

11:13 Um we know that it is not hard on quantum computers in the theoretical way to define them which um I think the largest number factorized on a on an practical quantum computer is five six or so. It's a they're not not quite there yet. Um but in terms of the computational complexity we we don't know. Integer factorization seems hard but we don't know. Maybe um maybe it could be um in some sneaky way allowing us some some efficient algorithm and we just haven't found it yet.

11:58 That's just as as an aside. So um what I'm showing you is is not the state-of-the-art uh for checking primes. In principle you can do deterministic polomial time. Now the algorithm itself is is complicated enough and the uh I think the degree of the polomial is is uh n to the 6 or so and it's not clear if you can do this much better. So practical implementations will very much use these randomized algorithms that we'll look at or slightly clever cleverer twists of those.

12:36 So does primes have this property that we have an abundance of witnesses? Let's try the obvious. And really I should have said uh not prime here because uh as I said there are certificates for primality but these are tricky. So um what I mean is can we expect to easily find factorizations for a non-prime number um if we just look at the factors the obvious approach to uh certify that a number is not prime that's not going to work right there's numbers that are just And so finding these is needle in a haststack. That's not going to work with randomly guessing numbers. Also, uh that's hardly um Because if that was possible, it would give you a factorization.

14:32 Right. Uh if I if I can guess a factor then I can produce the two uh uh I can produce a factorization of my number proving that it's composite and we've just discussed that that is unlikely or seems hard to do. So we have to work harder and we'll we'll do we'll have to need we'll have to to use something that indirectly certifies that a number is not prime but without explicitly giving you a factor. That's weird. How would that be possible? Uh well enter number theory and modulo and and finite fields and so on. Um there's various tools you can apply there. The simplest is Vermont's little theorem which just states what is written here. Uh for for every prime and uh a number between one and and the prime you could check that the raising that number to the prime power minus one is going to be equivalent to one modulo p. And so I'm not going to dive into any of the number theory parts here.

15:43 Um, so we could try to pick a random A in the range. So we're given some number P for which we want to check if it's prime.

16:08 So I guess checking means we compute this power modulo m modulo p and this exponentiation sounds expensive but you you may know if you do it modulo p there's actually efficient algorithms because you can you can always do modulo p because it's uh it's a field so you can compute in the small number field where everything is staying um below p.

16:42 So and if that is not equivalent to one then uh we know p is not a prime. Okay. Uh this is indeed uh sometimes used. It's called the verat primality test. Um it has one one problem that maybe some people know about. This is an implication. If we have a prime then this holds. It's not an equivalence.

17:10 So given that mathematicians try to be as precise in general as possible, if it's not formulated as an equivalence, there's probably some counter examples and in this case it's famous enough. These are called the Carmichael numbers.

17:45 uh which um satisfy this but aren't prime. Let's just give that a name here so I don't have to copy it. Uh so the primality test here is is relatively straightforward to do but it has this blind spot or well infin infinitely many blind spots where it it would erroneously say uh something is a prime because uh this is satisfied but it's the output should really be it's either prime or a carmichel number. So can we do better? Uh we need a more famous mathematician. Let's use Oiler. Um there's a criterion. Um that's named after him at least. Um if we have any odd number greater than two. Now this time it's a proper characterization. This number is prime if and only if the following is true for all numbers. And so this is uh the uh um I don't know uh it's the the the finite field of the integers is modulo um p that's what I what I mean by this um so if we take any any number not zero and take that number to the p minus one/2 power so that's why p has to be odd otherwise this is a bit of a trick a problem in integers then taking that modul p has to be either one or minus one and if that's true for all numbers in this field then p is prime that's an if and only if now so it's is a bit more convoluted how to use that um but at least now we could check this we won't want to check it exhaustively because that's a lot of numbers if p is big but we could check random A's and hope for the best. Right? If uh again if we find an A where this is violated, then we immediately know P is not prime. If we checked a lot of A's and they all satisfied the criterion, we could try to do the generalization and say maybe all of them do it. So let's let's claim P P is probably prime. Question.

20:22 Yeah, I guess it's P P minus one. uh just like uh I should probably have uh there's no nice element symbol that corresponds to the equivalent. Um it's a bit more memorable to write it that way. Yeah. Thanks. Thanks. Uh please ask questions if it's not clear.

20:48 Now this so this this could work but there's there's one catch um which is does this have this property of abundance of witness witnesses um and that's where things get uh slightly tricky but um is is not too bad. Uh we'll we'll just look at the easier part. So I'm assuming that I'm given a number that's not just odd but also n minus one half uh is odd. So it only works for for half of the odd numbers. Um then it's easy to show with this criterion that uh well first of all if if n is prime then that has to be true for all of these guys. Um that's from from above. Uh but if n is not prime then uh at least half of the numbers a from the um from the set here uh give a result that is not in in um one minus one. And so if I pick a random a I have a chance of 1/2 to pick uh an element that shows this. Um again the the proof is is more number theory than algorithms. So uh I'm I'm basically skipping this now for interest of time. Um you can show that you have some injective function from the numbers with that are not witnesses to the set of witnesses. So you can pair them up in a way and so uh the number of witnesses can't be smaller than the number of nonwitnesses where a non-witness here would be a number that's that's in this set one minus one if you take the power uh from this you can build um what's here called the simple solway stressen primality test because it it has this restriction that it only works for half of the odd numbers.

22:54 Uh this is a restriction you can easily lift. Um but again it's more number theory than than algorithms. The algorithm is as um as you would expect as I described. You pick a random number from the allowable range. You compute this this power modulo number and then just check uh if the number is in the expected set for a prime then we output it's probably a prime number. uh and otherwise it's not a prime and this is for short.

23:25 So it's uh basically we've already proven that this is a one-sided error Monte Carlo algorithm for the compositionality problem. So if I if I give you a composite number you'll probably find it with probability 1/2. Um if it's not composite namely prime then you'll you'll never going to um on that.

23:51 Now one-sided error Monte Carlo is good but for the wrong problem for the composite problem. Now if you want to formulate as a primality test then we can call it a two-sided error Monte Carlo where the one the error is in the other direction. Uh that's all that the corollery says. And this this restriction is just a reformulation of this condition.

24:22 I'm going to leave it with that uh because I'd rather show you some uh some interesting algorithm for for satisfiability. Uh there's one last thing you can do with this apart from checking for primes. You can also use use this to find uh a prime number a random or sample a random prime number which um is often a building block in in other algorithms. Um the algorithm is uh is relatively simple. Um we we keep trying for a certain number of uh of attempts. We generate a random bit string and interpret it as a number. It's a bit of a slightly um convoluted way to say uh that we generate a random odd number, but uh I wanted to explicitly show that you could do this from random bits. Maybe this is not so surprising. Um then we run the primality test um also a certain number of of times just to get more confident in the output uh probabilities boosting and uh if any of the outputs says this is uh this is not a prime then uh we try again. So, we increase the number of of failed attempts and otherwise we can output our prime number because we probably found one.

25:44 Okay. Uh and we fail if if we've used up too many attempts. Um let me state the theorem but I think I'm I'm also in the interest of time skipping the proof here.

26:22 So the claim is that uh if I call this with twice the same parameter then I get a two-sided aromonte cargo algorithm for generating primes.

27:00 where I'm using um Now some of the leading bits could be zero. So I guess it's uh it's a prime number of uh value at most 2 to the L. Uh what you have to show is one that the output is usually a prime and two it doesn't fail all the time. Uh that's the two claims. uh the fact that it um uses enough repetitions on an algorithm that has an error of 1/2 just means it's going to have an error of 2 to the minus k. Um is actually a stronger than what we would require for just Monte Carlo.

28:40 And it doesn't fail with this uh statement. No prime number found um with a probability of of 1 over 2 L. So again uh much stronger than what we need. Uh so you could reduce the number of iterations if you just wanted the 1/2. Uh the only interesting part is we're picking a random odd number. How likely is that to be a prime? Let's ignore the the second part. We're also checking for primes with a with a potentially faulty method that sometimes doesn't um which way around is it? It may sometimes say uh it's a probably a prime but it may sometimes eronously say that. Okay, so it's a bit uh in in the two directions. Um but let's suppose this this test was perfect. How likely is it that we hit a a prime number if we just randomly sample a number?

29:57 So apart from the standard analysis we've done many times So uh we we actually force the first bit to be one here. So the n is sampled uniformly in the range 2 to the l up to 2 to the uh sorry l minus one up to 2 to the l. So it's a random odd number from that range. How likely is that to be a prime number? And so this is where you need an ingredient from number theory again and this I think is is useful enough to at least roughly have in in mind. So, prime number theorem, you likely saw some statement of this in some introductory uh module, but often not formulated in the computer sciency way. Um, pi of x is a function which denotes the number of primes less or equal x. And the prime number theorem says that this is asmtoic to x / ln x.

31:49 Okay. And so well what does it mean? The fraction of numbers which are prime is going to zero because out of x numbers only x divided log n x are prime. But also is is a fairly large fraction. And I always found that surprising that there's so many primes. Also, the number of primes. If you if you look at the distance between two consecutive primes, this is like a very chaotic sequence. Sometimes you have these twin primes where the distance is just two and I think it's still open whether there's infinitely many of them and all these things. And then there's sometimes long jumps between primes. But if you smooth things out by integrating just counting how many primes are before a certain point uh then you get this fairly clean and and and simple description that at least asmtoically gives you a nice number. And so you can maybe now imagine um you have a from this range there's going to be roughly 2 to the L divided L many primes. So you have a chance of of one in L to pick one. So you have to sample L times in expectation to get one. I'm not going to do the full math here. It's something we've we've seen a few times now. Um so the overall running time for the algorithm I think is is maybe useful uh just to state because uh L to the 5th is also not not that great. Okay.

33:26 So I just wanted to throw this piece of knowledge out without much more content or more context.