Question

Problem 3.7. We wish to use the AKS algorithm to test whether 211 is a prime number explanation of AKS. 24 a)211 See the wikipedia reference for a concise ex 1. Use a computer to compute if ( 211a (mod 211) for a suitable choice of a. Be sure to explain why your choice of a is allowed. Does this allow us to conclude -T211 that 211 is prime? 2. Compute our upper bound r < n using the AKS algorithm

Answer 1

we wish to use the AKS algorithm to test whether 211 is a prime number 1. Forn = 211 & a = 1 the AKS primality succeeds a = 1 is allowed since 1 & 211 are Coprime For n = 211 & a = 2 the AKS primality succeeds a = 2 is allowed since 2 & 211 are Coprime For n = 211 & a = 3 the AKS primality succeeds a = 3 is allowed since 3 & 211 are Coprime Hence 211 is a prime number 2. for r < n, the time complexity of the AKS primality test is 0 (n^6), where n is the length of the input