| Institution: | University of Waterloo, Department of Combinatorics and Optimization, Waterloo, Ontario, Canada N2L 3G1 ; University of Manitoba, Department of Computer Science, Winnipeg, Manitoba, Canada R3T 2N2 |
| Abstract: | Deterministic polynomial time primality criteria for  have been known since the work of Lucas in 1876-1878. Little is known, however, about the existence of deterministic polynomial time primality tests for numbers of the more general form  , where  is any fixed prime. When  we show that it is always possible to produce a Lucas-like deterministic test for the primality of  which requires that only  modular multiplications be performed modulo  , as long as we can find a prime  of the form  such that  is not divisible by  . We also show that for all  with  such a  can be found very readily, and that the most difficult case in which to find a  appears, somewhat surprisingly, to be that for  . Some explanation is provided as to why this case is so difficult. |
