IJPAM: Volume 44, No. 3 (2008)


David P. Jacobs$^1$, Mohamed O. Rayes$^2$, Vilmar Trevisan$^3$
$^1$School of Computing
Clemson University
Clemson, SC 29634-0974, USA
e-mail: dpj@cs.clemson.edu
$^2$Department of Computer Science and Engineering
Southern Methodist University
Dallas, TX 75275-0122, USA
e-mail: mrayes@engr.smu.edu
$^3$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-$n$ Chebyshev polynomial of the second kind. Rankin showed that if $p$ 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 $a$ for which $ {a^2 - 1 \overwithdelims() p} = -1$ and $ {a^2 - 1 \overwithdelims() p} = 1$ respectively. We show that when $n$ is an odd composite, at least half of the members $a \in \Zn$ are witnesses, unless $n = pq$ where $p$ and $q$ 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 $a$, the other two requiring only an additional guess.

Received: January 1, 2008

AMS Subject Classification: 11Y11, 68W20

Key Words and Phrases: primality, randomized algorithms, Chebyshev polynomial

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2008
Volume: 44
Issue: 3