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: dpj@cs.clemson.edu

Department of Computer Science and Engineering
Southern Methodist University
Dallas, TX 75275-0122, USA
e-mail: mrayes@engr.smu.edu

Instituto de Matemática, UFRGS
Porto Alegre, 91509-900, BRAZIL
e-mail: trevisan@mat.ufrgs.br

Abstract.We consider a simple, fast randomized compositeness test. Let $\chebU{n}{x}$ denote the degree- Chebyshev polynomial of the second kind. Rankin showed that if is an odd prime, then exactly $\frac{p-1}{2}$ of the numbers $a \in \Zp - \left\{ 1, -1 \right\}$ , satisfy $\leftUp{a} \equiv 0 \bmod p$ , and the remaining $\frac{p-3}{2}$ numbers satisfy $\rightUp{a} \equiv 0 \bmod p$ . Moreover, these are precisely the numbers for which ${a^2 - 1 \overwithdelims() p} = -1$ and ${a^2 - 1 \overwithdelims() p} = 1$ respectively. We show that when is an odd composite, at least half of the members $a \in \Zn$ are witnesses, unless where and are twin primes, in which case there must be at least $\frac{3}{8}n$ 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.