5), p is odd so p+1 is even and this automatically won't happen when n is even. If n is odd, then we can factor n+1 (in n^o(1) time if one uses a fast algorithm) and list all tau(n+1) divisors d of n+1 which are large enough, and see if d-1 is prime (using a Lucas test, since the factorization of (d-1)+1=d is already known). tau(n+1) is also n^o(1) and the primality testing for d-1 can be done very quickly. If one directly tests n with respect to all p < n^(1/2) after doing this, then one obtains a test which runs in n^(1/2+o(1)) time. But these ideas can be extended further: Suppose p is large enough that n<=p^3+p^2+p-2. Then n < p(p^2+p+1) so we may write n = c(p^2+p+1) + r1, where 0 <= c < p and 0 <= r1 < p^2+p+1. If r1 = p^2+p, then r1 > (p-1)(p+1)+ (p-1)*1 so n fails the base p test at this first step. This kind of failure is easy to detect quickly because n = c(p^2+p+1) + p^2+p means p^2+p+1 divides n+1 so that we can just do a divisor search (and use the fact that all prime factors of p^2+p+1, aside from 3, must be congruent to 1 mod 3, and 3 itself may appear only once in the factorization of p^2+p+1) and a primality test (the idea of the Lucas test can be adapted here, if one is not willing to settle for a fast general-purpose primality test: we are testing m=(-1+sqrt(4d-3))/2 for primality and we know the factorization of m^2+m+1, so we can use a primality test which uses third-order linear recurrence sequences instead of the second-order ones used in the Lucas test). This is failure at the first step in the base p test, and it can be eliminated for all c with one big factorization+divisor list+primality test. If r1<=p^2+p-1, then we may write r1 = a(p+1) + b as before so that n = c*(p^2+p+1) + a(p+1) + b and, as before, ), 0<=a

12, p=2 isn't a problem and p+1 is even so this test is immediately passed if n+1-c is odd. This means only those values of c incongruent to n mod 2 need to be tested. This takes n^o(1) time for each of the approximately n^(1/3)/2 values of c tested. So this overall takes n^(1/3+o(1)) steps. For all primes p with p^3+p^2+p-2 < n, the direct test is still used on each one. This takes n^(1/3+o(1)) steps also.