### The Ultimate Primality Test

Figuring out whether or not a number is prime has been a long quest by mathematicians and computer scientists, especially in the last 50 years with the development of computer cryptography, in particular the RSA algorithm. The common, centuries-old method for checking whether a number N is prime is very straightforward: test all the numbers "i" between 2 and SQRT(N), and if N is divisible by "i" then N is not prime, otherwise it is prime. There is a number of optimizations to this algorithm, but its core remains the same, and so does the lower bound execution time of O(SQRT(N)). Which works well for N = 32212254719, since SQRT(N) ~= 179478. However - try this: N = 225251798594466661409915431774713195745814267044878909733007331390393510002687. This is a special prime number, one of the Woodall prime numbers . Out of curiosity, its root square is 4.74606994E38, which becomes intractable. What are the options? The best primality test algorithm was actually discovere