# IJPAM: Volume 44, No. 3 (2008)

RANDOMIZED COMPOSITENESS TESTING
WITH CHEBYSHEV POLYNOMIALS

David P. Jacobs, Mohamed O. Rayes, Vilmar Trevisan
School of Computing
Clemson University
Clemson, SC 29634-0974, USA
e-mail: [email protected]
Department of Computer Science and Engineering
Southern Methodist University
Dallas, TX 75275-0122, USA
e-mail: [email protected]
Instituto de Matemática, UFRGS
Porto Alegre, 91509-900, BRAZIL
e-mail: [email protected]

Abstract.We consider a simple, fast randomized compositeness test. Let denote the degree- Chebyshev polynomial of the second kind. Rankin showed that if is an odd prime, then exactly of the numbers , satisfy , and the remaining numbers satisfy . Moreover, these are precisely the numbers for which and respectively. We show that when is an odd composite, at least half of the members are witnesses, unless where and are twin primes, in which case there must be at least witnesses. However, these ratios occur only for a rare set of numbers, and in practice the expected ratio of witnesses is very high. In one experiment involving a million large composite numbers, all but two composites were recognized with the first randomly chosen , the other two requiring only an additional guess.